【进阶篇 - Day 34】 2020-11-04 - 树的遍历系列（07. 高频面试题 ）

入选理由

1. 面试频率高
2. 锻炼大家对栈的灵活应用

题目描述

144. 二叉树的前序遍历(迭代和递归) (opens new window) > 94. 二叉树的中序遍历(迭代和递归) (opens new window) > 145. 二叉树的后序遍历(迭代和递归) (opens new window) > 102. 二叉树的层序遍历 (迭代和递归) (opens new window)

我的回答

https://github.com/leetcode-pp/91alg-2/issues/60#issuecomment-738540329

前序遍历

递归解法

var preorderTraversal = function (root, ans = []) {
    if (!root) return []
    ans.push(root.val)
    let left = preorderTraversal(root.left, ans)
    let right = preorderTraversal(root.right, ans)
    return ans
};

迭代解法

var preorderTraversal = function (root) {
    if (!root) return []
    //white代表还没进过栈,gray 代表已经进过栈
    let stack = [['white', root]]
    let ans = []
    while (stack.length) {
        let [color, node] = stack.pop()
        if (!node) continue
        if (color === 'white') {
            // 先right,后left,因为先进后出
            stack.push(['white', node.right])
            stack.push(['white', node.left])
            stack.push(['gray', node])
        } else {
            ans.push(node.val)
        }
    }
    return ans
};

中序遍历

递归

var inorderTraversal = function (root, ans = []) {
    if (!root) return []
    let left = inorderTraversal(root.left, ans)
    ans.push(root.val)
    let right = inorderTraversal(root.right, ans)
    return ans
};

迭代

var inorderTraversal = function (root) {
    if (!root) return []
    let stack = [['white', root]]
    let ans = []
    while (stack.length) {
        let [color, node] = stack.pop()
        if (!node) continue
        if (color == 'white') {
            stack.push(['white', node.right])
            stack.push(['gray', node])
            stack.push(['white', node.left])
        } else {
            ans.push(node.val)
        }
    }
    return ans
};

后序遍历

枯燥的背模板

递归

var postorderTraversal = function (root, ans = []) {
    if (!root) return []
    let left = postorderTraversal(root.left, ans)
    let right = postorderTraversal(root.right, ans)
    ans.push(root.val)
    return ans
};

迭代

var postorderTraversal = function (root) {
    if (!root) return []
    let stack = [['white', root]]
    let ans = []
    while (stack.length) {
        let [color, node] = stack.pop()
        if (!node) continue
        if (color == 'white') {
            stack.push(['gray', node])
            stack.push(['white', node.right])
            stack.push(['white', node.left])
        } else {
            ans.push(node.val)
        }
    }
    return ans
};

层序遍历

菜的抠脚 ，以为层序遍历最熟没想到写了最久

迭代写法

var levelOrder = function (root) {
    if (!root) return []
    let queue = [root]
    let ans = []
    while (queue.length) {
        let levelArr = []
        let length = queue.length
        for (let i = 0; i < length; i++) {
            let curr = queue.shift()
            curr.left && queue.push(curr.left)
            curr.right && queue.push(curr.right)
            levelArr.push(curr.val)
        }
        ans.push(levelArr)
    }
    return ans
};

递归写法

var levelOrder = function (root, ans = [], depth = 0) {
    if (!root) return []
    ans[depth] = ans[depth] || []
    ans[depth].push(root.val)
    levelOrder(root.left, ans, depth + 1)
    levelOrder(root.right, ans, depth + 1)
    return ans
};

参考回答

• [官方题解](https://github.com/leetcode-pp/91alg-2/blob/master/solution/advanced/d34 tree.md)