Binary Tree Inorder Traversal (M)
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
题意
求树的中序遍历。
思路
递归或者迭代。
另有一种神奇的既不使用栈也不用递归的遍历方法,参考 Inorder Tree Traversal without recursion and without stack!。(官方解答改变了树的结构却没有恢复原状)
代码实现 - 递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inorder(root, ans);
return ans;
}
private void inorder(TreeNode x, List<Integer> ans) {
if (x == null) {
return;
}
inorder(x.left, ans);
ans.add(x.val);
inorder(x.right, 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<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
ans.add(cur.val);
cur = cur.right;
}
return ans;
}
}
代码实现 - O(1)空间迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode r = cur.left;
while (r.right != null && r.right != cur) {
r = r.right;
}
if (r.right == null) {
r.right = cur;
cur = cur.left;
} else {
r.right = null;
ans.add(cur.val);
cur = cur.right;
}
} else {
ans.add(cur.val);
cur = cur.right;
}
}
return ans;
}
}