跳到主要内容

33 篇博文 含有标签「树」

查看所有标签

· 阅读需 4 分钟

1、题干​

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

 

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

 

提示:

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

 

注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/

2、解法1​

使用DFS递归遍历树的所有节点，递归函数接收上层传递下来的路径上所有前缀和，遍历所有前缀和并计算是否存在和等于targetSum的路径（计算公式node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum），存在则最终结果+1，时间复杂度为O(nlogn)O(nlogn)。

上述时间复杂度是估算值，因为每个节点需要访问一次，因此至少有O(n)O(n)的复杂度，另外每个节点内部需要再遍历前缀和数组，而数组长度最大为树的最大高度lognlogn，因此综合估算时间复杂度为O(nlogn)O(nlogn)。

3、代码​

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = root.val === targetSum ? 1 : 0;

    function dfs(node, sums) {
        if (!node) return;
        for (let i = -1; i < sums.length; i++) {
            if (node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum) res++;
        }

        dfs(node.left, [...sums, (sums[sums.length - 1] || 0) + node.val]);
        dfs(node.right, [...sums, (sums[sums.length - 1] || 0) + node.val]);
    }

    return dfs(root, []), res;
};

4、执行结果​

执行用时: 148 ms 内存消耗: 57.8 MB

5、解法2​

该解法是解法1的优化版本，利用了哈希表存储前缀和，另外使用了回溯的思想重置前缀和状态，优化后的时间复杂度为O(n)O(n)。

  • 同样使用DFS递归遍历树的所有节点，但使用Map存储前缀和及其数量，递归时在Map中查找是否已存在等于sum - targetSum的路径前缀和，存在则最终结果累加其数量
  • 将当前路径总和对应的数量累加1
  • 然后进入下层递归，同样执行上述逻辑
  • 下层递归结束时，将当前路径总和对应的数量累减1

6、代码​

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = 0, map = new Map();
    map.set(0, 1);

    function dfs(node, sum) {
        if (!node) return;
        sum = sum + node.val;
        res += map.get(sum - targetSum) || 0;
        map.set(sum, (map.get(sum) || 0) + 1);
        dfs(node.left, sum);
        dfs(node.right, sum);
        map.set(sum, map.get(sum) - 1);
    }

    return dfs(root, 0), res;
};

7、执行结果​

1.png

· 阅读需 4 分钟

1、题干​

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

 

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

 

提示:

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

 

注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/

2、解法1​

使用DFS递归遍历树的所有节点，递归函数接收上层传递下来的路径上所有前缀和，遍历所有前缀和并计算是否存在和等于targetSum的路径（计算公式node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum），存在则最终结果+1，时间复杂度为O(nlogn)O(nlogn)。

上述时间复杂度是估算值，因为每个节点需要访问一次，因此至少有O(n)O(n)的复杂度，另外每个节点内部需要再遍历前缀和数组，而数组长度最大为树的最大高度lognlogn，因此综合估算时间复杂度为O(nlogn)O(nlogn)。

3、代码​

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = root.val === targetSum ? 1 : 0;

    function dfs(node, sums) {
        if (!node) return;
        for (let i = -1; i < sums.length; i++) {
            if (node.val + sums[sums.length - 1] - (sums[i] || 0) === targetSum) res++;
        }

        dfs(node.left, [...sums, (sums[sums.length - 1] || 0) + node.val]);
        dfs(node.right, [...sums, (sums[sums.length - 1] || 0) + node.val]);
    }

    return dfs(root, []), res;
};

4、执行结果​

执行用时: 148 ms 内存消耗: 57.8 MB

5、解法2​

该解法是解法1的优化版本，利用了哈希表存储前缀和，另外使用了回溯的思想重置前缀和状态，优化后的时间复杂度为O(n)O(n)。

  • 同样使用DFS递归遍历树的所有节点，但使用Map存储前缀和及其数量，递归时在Map中查找是否已存在等于sum - targetSum的路径前缀和，存在则最终结果累加其数量
  • 将当前路径总和对应的数量累加1
  • 然后进入下层递归，同样执行上述逻辑
  • 下层递归结束时，将当前路径总和对应的数量累减1

6、代码​

var pathSum = function (root, targetSum) {
    if (!root) return 0;
    let res = 0, map = new Map();
    map.set(0, 1);

    function dfs(node, sum) {
        if (!node) return;
        sum = sum + node.val;
        res += map.get(sum - targetSum) || 0;
        map.set(sum, (map.get(sum) || 0) + 1);
        dfs(node.left, sum);
        dfs(node.right, sum);
        map.set(sum, map.get(sum) - 1);
    }

    return dfs(root, 0), res;
};

7、执行结果​

1.png

· 阅读需 5 分钟

1、题干​

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

  • 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
  • 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
  • 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

 

示例 1：

输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。

示例 2：

输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

示例 3：

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。

示例 4：

输入：root = [1]
输出：true

示例 5：

输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出：true

 

提示：

  • 树中节点数在范围 [1, 105] 内
  • 1 <= Node.val <= 106

2、解题思路​

使用广度优先遍历(BFS)或深度优先遍历(DFS)，遍历树上所有节点并判断其是否符合奇偶树的特性。

  • 使用广度优先遍历(BFS)时，比较方便做到按层遍历、获取层级和兄弟节点
  • 使用深度优先遍历(DFS)时，需要另外使用一个数组存储每层上一次遍历到的节点，用于判断兄弟节点的单调性

3、代码1-DFS递归实现​

执行用时：212 ms 内存消耗：82.4 MB

var isEvenOddTree = function (root) {
  const nums = [];
  function dfs(node, i) {
    if (!node) return true;
    if (i % 2 && (node.val % 2 || node.val >= nums[i])) return false;
    if (!(i % 2) && (!(node.val % 2) || node.val <= nums[i])) return false;
    nums[i] = node.val;
    return dfs(node.left, i + 1) && dfs(node.right, i + 1);
  }
  return dfs(root, 0);
};

4、代码2-BFS递归实现​

执行用时：308 ms 内存消耗：98 MB

var isEvenOddTree = function (root) {
  function bfs(nodes, i) {
    const nextArr = [];
    for (let j = 0; j < nodes.length; j++) {
      if (nodes[j].left) nextArr.push(nodes[j].left);
      if (nodes[j].right) nextArr.push(nodes[j].right);

      const m1 = i % 2, m2 = nodes[j].val % 2;
      if (m1 && (m2 || (j && nodes[j].val >= nodes[j - 1].val))) return false;
      if (!m1 && (!m2 || (j && nodes[j].val <= nodes[j - 1].val))) return false;
    }
    return !nextArr.length ? true : bfs(nextArr, i + 1);
  }
  return bfs([root], 0);
};

5、代码3-BFS非递归实现​

执行用时：276 ms 内存消耗：91.5 MB

var isEvenOddTree = function (root) {
  const queue = [[root]];
  for (let i = 0; i < queue.length; i++) {
    const nextArr = [];

    for (let j = 0; j < queue[i].length; j++) {
      if (queue[i][j].left) nextArr.push(queue[i][j].left);
      if (queue[i][j].right) nextArr.push(queue[i][j].right);

      const m1 = i % 2, m2 = queue[i][j].val % 2;
      if (m1 && (m2 || (j && queue[i][j].val >= queue[i][j - 1].val))) return false;
      if (!m1 && (!m2 || (j && queue[i][j].val <= queue[i][j - 1].val))) return false;
    }

    if (nextArr.length) queue.push(nextArr);
  }

  return true;
};

6、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

 

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2

示例5：

输入: root = []
输出: []

 

提示：

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

 

注意：本题与主站 515 题相同： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/

解法1：DFS递归实现​

DFS递归遍历树的每个节点，递归函数的形参中添加1个层级参数，便于计算每层节点最大值。

执行结果​

1.png

代码​

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

解法2：BFS非递归实现​

BFS非递归遍历树的每个节点，需要借助队列实现。与常规BFS非递归实现不同，此处队列是一个矩阵，队列中的元素是每层节点的集合。

执行结果​

2.png

代码​

var largestValues = function (root) {
    const queue = root ? [[root]] : [], res = [];
    for (const curNodes of queue) {
        let max = -Infinity, nodes = [];
        for (const node of curNodes) {
            if (node.val > max) max = node.val;
            if (node.left) nodes.push(node.left);
            if (node.right) nodes.push(node.right);
        }
        if (nodes.length) queue.push(nodes);
        res.push(max);
    }
    return res;
};

由于非递归实现需要额外借助数组实现，且存在大量Array.push()等耗时操作，所以时间和空间上会消耗得更多

· 阅读需 2 分钟

1、题干​

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

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

 

提示:

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

 

注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/

执行结果​

2.png

解题思路​

总体思路：使用DFS递归遍历树的所有节点，当第一次遍历到层级大于所有已遍历节点的节点时，该节点就是当前层级的最左子节点；随着遍历层级递增，最终能找到最底层的最左子节点。

  • 使用DFS递归遍历树的所有节点
  • 记录当前节点的层级level与已遍历节点的最大层级maxLevel
  • 每当level超过maxLevel时，将当前节点赋值给res，另外更新maxLevel
  • 遍历完成后，res就是要找的节点，返回该节点的值即可

代码​

var findBottomLeftValue = function (root) {
    let res, maxLevel = 0;
    function dfs(node, level) {
        if (!node) return;
        if (level > maxLevel) res = node, maxLevel = level;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 1);
    return res && res.val;
};

· 阅读需 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);
};

· 阅读需 3 分钟

1、题干​

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

 

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
          1
         / \
        3   2
       / \   \  
      5   3   9

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
          1
         / \
        2   3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:      
           1 
            \
             2

示例5：

输入: root = []
输出: []

 

提示：

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

 

注意：本题与主站 515 题相同： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/

解法1：DFS递归实现​

DFS递归遍历树的每个节点，递归函数的形参中添加1个层级参数，便于计算每层节点最大值。

执行结果​

1.png

代码​

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

解法2：BFS非递归实现​

BFS非递归遍历树的每个节点，需要借助队列实现。与常规BFS非递归实现不同，此处队列是一个矩阵，队列中的元素是每层节点的集合。

执行结果​

2.png

代码​

var largestValues = function (root) {
    const queue = root ? [[root]] : [], res = [];
    for (const curNodes of queue) {
        let max = -Infinity, nodes = [];
        for (const node of curNodes) {
            if (node.val > max) max = node.val;
            if (node.left) nodes.push(node.left);
            if (node.right) nodes.push(node.right);
        }
        if (nodes.length) queue.push(nodes);
        res.push(max);
    }
    return res;
};

由于非递归实现需要额外借助数组实现，且存在大量Array.push()等耗时操作，所以时间和空间上会消耗得更多

· 阅读需 2 分钟

1、题干​

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

 

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

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

 

提示:

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

 

注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/

执行结果​

2.png

解题思路​

总体思路：使用DFS递归遍历树的所有节点，当第一次遍历到层级大于所有已遍历节点的节点时，该节点就是当前层级的最左子节点；随着遍历层级递增，最终能找到最底层的最左子节点。

  • 使用DFS递归遍历树的所有节点
  • 记录当前节点的层级level与已遍历节点的最大层级maxLevel
  • 每当level超过maxLevel时，将当前节点赋值给res，另外更新maxLevel
  • 遍历完成后，res就是要找的节点，返回该节点的值即可

代码​

var findBottomLeftValue = function (root) {
    let res, maxLevel = 0;
    function dfs(node, level) {
        if (!node) return;
        if (level > maxLevel) res = node, maxLevel = level;
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 1);
    return res && res.val;
};