跳到主要内容

31 篇博文 含有标签「二叉树」

查看所有标签

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

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