阅读 36

LeetCode二叉树层次遍历(binary-tree-level-order-traversal-ii)

一、主题

  • 难度:简单

  • 涉及知识:树、广度优先搜索

  • 题目地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

  • 题目内容

    给定一个二叉树,返回其节点自底向上的层次遍历
    (即从叶子节点所在层到根节点所在层,逐层从左到右遍历,总体以数组形式呈现,每层以子数组形式呈现)
    
    e.g.
    给定一个二叉树[3,9,20,null,null,15,7]
    
    图形呈现:
        3
       / \
      9  20
        /  \
       15   7
    
    返回自底向上遍历该二叉树的数组:
    [
     [15,7],
     [9,20],
     [3]
    ]
    复制代码


二、解题

  • 用例:

    题目给定用例:[3,9,20,null,null,15,7]
    
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[][]}
     */
    由编辑器顶部给定的形式,可判断二叉树root的结构为
    输入方法的参数root,即测试用例如下:
    let root = {
        val: 3,
        left: {
            val: 9, left: null, right: null
        },
        right: {
            val: 20,
            left: {
                val: 15, left: null, right: null
            },
            right: {
                val: 7, left: null, right: null
            }
        }
    };复制代码

  • 解题步骤:

/**
 * 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) {
    if (!root) {
        return [];//输入的方法root为空,则代表这是个空的二叉树
    }
    let result = [];

    //遍历root的方法,depth表示遍历到二叉树的哪一层,初始时候为0(即第一层),运行后在方法内进行自增
    let showList = function (root, depth) {
        if (!root || root.val == null) {
            return; //输入的二叉树节点为空,或节点值为空
        }
        //查找本层级是否已经有遍历
        if (!result[depth]) {
            result[depth] = [];//如果没有被遍历则初始化该层为一个数组,其中一个层级理解为一个子数组
        }
        result[depth] = [root.val,...result[depth]
    ]
        ;//此处为es6扩展符写法,意为将root.val推入result[depth]原有项
        depth += 1;
        showList(root.right, depth);//由于是遍历的val值插入同层级子数组的最前一项,所以要先遍历right子节点,才能形成最后左节点在右节点前项
        showList(root.left, depth);
    };
    showList(root, 0);

    return result.reverse();//由于题目要求是从底层往顶层输出遍历结果,则只需要reverse处理即可
};
复制代码

  • 解题思路:
    • 后续遍历(LRC)思路

 遍历顺序为:3,20,7,15,9  然后依次插入对应层级depth的子数组
复制代码

    • depth层级参数

depth在方法中既表示层级,也表示层级对应的子数组编号,在遍历结果result中充当对应关系。复制代码


关注下面的标签,发现更多相似文章
评论