94.二叉树的中序遍历

94.二叉树的中序遍历

30min

中序遍历的顺序是 左 - 中 - 右

递归

用递归非常容易

1
2
3
4
5
6
7
8
9
10
11
12
13
var inorderTraversal = function(root) {
var res = []
if (!root) {
return res
}
var travel = function (node) {
node.left && travel(node.left)
res.push(node.val)
node.right && travel(node.right)
}
travel(root)
return res
};
迭代

迭代的步骤复杂一些,因为根节点不是先输出,所以需要保留根节点

  1. 根节点入栈,判断有没有左子节点,如果有,继续入栈,直到叶子结点
  2. 出栈,输出,判断是否有右子节点,有则入栈,继续执行2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var inorderTraversal = function(root) {
var stack = []
var res = []
if (!root) return res
stack.push(root)
while(root.left) {
stack.push(root.left)
root = root.left
}
while(stack.length) {
// 此时栈顶是树中最左的节点
var node = stack.pop()
res.push(node.val)
// 存在右节点,入栈后继续找左节点
if (node.right) {
node = node.right
stack.push(node)
while(node.left) {
stack.push(node.left)
node = node.left
}
}
}
return res
};