- 描述
Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree
{1, #, 2, 3}, return [1, 3, 2].
Note: Recursive solution is trivial, could you do it iteratively?
- 时间复杂度O(n)，空间复杂度O(n)
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution {
public static List<Integer> inorderTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()) {
if(p != null) {
stack.push(p);
p = p.left;
}
else {
p = stack.pop();
result.add(p.val);
p = p.right;
}
}
return result;
}
}
