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
};