ChuChencheng / note

菜鸡零碎知识笔记
Creative Commons Zero v1.0 Universal
3 stars 0 forks source link

二叉树的层次遍历 II #6

Open ChuChencheng opened 4 years ago

ChuChencheng commented 4 years ago

问题

LeetCode

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

返回其自底向上的层次遍历为:

[
[15,7],
[9,20],
[3]
]

与 #5 类似

DFS

在 #5 的基础上稍作修改

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    const result = []
    if (!root) return result
    const stack = [[root, 0]]
    while (stack.length) {
        const info = stack.pop()
        const node = info[0]
        const level = info[1]
        if (node) {
            if (result.length <= level) result.unshift([])
            result[result.length - 1 - level].push(node.val)
            stack.push([node.right, level + 1])
            stack.push([node.left, level + 1])
        }
    }
    return result
};