94.二叉树的中序遍历

30min

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

递归

用递归非常容易

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