跳到主要内容

33 篇博文 含有标签「树」

查看所有标签

· 阅读需 2 分钟

1、题干​

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

 

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

 

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100 

 

注意：本题与主站 199 题相同：https://leetcode-cn.com/problems/binary-tree-right-side-view/

执行结果​

0.png

解题思路​

总体思路：使用DFS递归遍历树的所有节点，创建结果数组res，将当前节点的层级当做res的下标、val当做res的值，以此更新res，右边节点的值会不断覆盖左边节点，得到的数组就是从右侧所能看到的节点值。

代码​

var rightSideView = function (root) {
    const res = [];
    function dfs(node, level) {
        if (!node) return;
        res[level] = node.val;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return res;
};

· 阅读需 2 分钟

1、题干​

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

 

示例 1:

输入: [1,null,0,0,1]
输出: [1,null,0,null,1] 
解释: 
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。


示例 2:

输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
解释:


示例 3:

输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
解释:


 

提示:

  • 二叉树的节点个数的范围是 [1,200]
  • 二叉树节点的值只会是 0 或 1

 

注意：本题与主站 814 题相同：https://leetcode-cn.com/problems/binary-tree-pruning/

执行结果​

1.png

解题思路​

总体思路：使用DFS递归遍历树的节点，递归过程中把值为0的叶子节点逐个剪除，就能得到剪枝后的二叉树。

代码​

var pruneTree = function (root) {
    function dfs(node) {
        if (!node) return;
        if (dfs(node.left)) node.left = null;
        if (dfs(node.right)) node.right = null;
        if (node.val === 0 && !node.left && !node.right) return true;
    }
    return dfs(root) ? null : root;
};

· 阅读需 3 分钟

1、题干​

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

 

提示：

  • 树中节点的数目在范围 [1, 1000] 内
  • 0 <= Node.val <= 9
  • 树的深度不超过 10

 

注意：本题与主站 129 题相同： https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

执行结果​

1.png

解题思路​

总体思路：DFS递归遍历所有节点，递归函数增加一个形参path，用于记录根节点到当前节点这条路径上所有数字拼接成的字符串，最后把所有path转成数字并累加即可。

官解直接使用10进制计算，时长和内存都会低一些。这个解法思路算简单，时间复杂度和空间复杂度也跟官解一样，但执行时长和内存消耗略高，问题主要在以下两点：

  • 时间主要消耗在：paths.push()、字符串累加、最后多了一步paths转换累加
  • 内存主要消耗在：存储paths、每个dfs调用栈的字符串形参path、末尾的paths.reduce的回调函数的调用栈空间

代码​

var sumNumbers = function (root) {
    const paths = [];
    function dfs(node, path) {
        if (!node) return;
        if (!node.left && !node.right) paths.push(path + node.val);
        dfs(node.left, path + node.val);
        dfs(node.right, path + node.val);
    }
    dfs(root, '');
    return paths.reduce((acc, cur) => +cur + acc, 0);
};