本文共 1503 字，大约阅读时间需要 5 分钟。
##给定一个二叉树，返回它的中序遍历。 示例:输入: [1,null,2,3]
1 2 / 3输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 栈。时间复杂度O(n)，空间复杂度O(lgn)。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private void recur(TreeNode root, List ans) { if(root != null) { if(root.left != null) { recur(root.left, ans); } ans.add(root.val); if(root.right != null) { recur(root.right, ans); } } } public List inorderTraversal(TreeNode root) { List ans = new ArrayList (); recur(root, ans); return ans; }} /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List inorderTraversal(TreeNode root) { List ans = new ArrayList (); Stack stack = new Stack (); TreeNode curr = root; while(curr != null || !stack.isEmpty()) { while(curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); ans.add(curr.val); curr = curr.right; } return ans; }} 链接：
转载地址：http://ofuki.baihongyu.com/