S*******C
发帖数: 822 | 1 public List inorderTraversal(TreeNode root) {
List res = new ArrayList();
if (root == null)
return res;
Stack stack = new Stack();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
// if it is not null, push to stack
//and go down the tree to left
if (p != null) {
stack.add(p);//stack.push(p);
p = p.left;
} else {// if no left child,
//pop stack, process the node
// then let p point to the right
p = stack.pop();
res.add(p.val);
p = p.right;
}
}
return res;
} |
S*******C
发帖数: 822 | |
d********o
发帖数: 12 | 3 这种方法确实是O(h)
如果用Morris Traversal，空间复杂度O(1)
【在 S*******C 的大作中提到】
: 知道了，是O(h)
|
S*******C
发帖数: 822 | 4 连Morris Traversal都会写的人至少刷了500道题吧
【在 d********o 的大作中提到】
: 这种方法确实是O(h)
: 如果用Morris Traversal，空间复杂度O(1)
|
s*********3
发帖数: 25 | 5 如果N是树的深度， 那么就是O(N).
如果N是节点的个数， 那么就看树是不是balance，如果是balance，那么就是O(logN). |
