Given a binary tree, return the inorder traversal of its nodes' values.
和preorder基本一样。把所有左节点压入栈中, 区别在于preorder是结果(加入res list的顺序)跟着cur走。而inorder是结果跟着弹出的顺序走,因为弹出意味着它的左子树都已遍历完,该root结点了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private void pushLefts(Stack<TreeNode> stack, TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
pushLefts(stack, root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
pushLefts(stack, node.right);
}
return res;
}
}
时空复杂度都是O(N).