一、计算二叉树的最大深度

题目(LT104. 二叉树的最大深度)
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

  1. 3

/ \ 9 20 / \ 15 7

返回它的最大深度 3 。

解题思路

  • 求最大深度，优先考虑深度优先遍历；

  • 在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可；

    1. var maxDepth = function(root) {
    2.   let depth = 0
    4.   const preorder = (root, depth) => {
    5.       if(!root) return depth
    7.       let leftDepth = preorder(root.left, depth + 1)  // 计算左子树的最大深度
    8.       let rightDepth = preorder(root.right, depth + 1) // 计算右子树的最大深度
    10.       return Math.max(leftDepth, rightDepth)  // 取最大值
    11.   }
    13.   return preorder(root, depth)
    14. };

    此处采用二叉树先序遍历来计算最大深度，其中时间复杂度是O(N)。该算法使用了隐形的栈数据结构，最差的空间复杂度是O(N)，即每个二叉树都是单节点；最好的空间复杂度是O(logN)，即都是均匀分布。

二、计算二叉树的最小深度

题目(LT111.二叉树的最小深度)
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
image.png

输入：root = [3,9,20,null,null,15,7] 输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

提示：

  • 树中节点数的范围在 [0, 105] 内
  • -1000 <= Node.val <= 1000

解题思路

  • 求最小深度，考虑使用广度优先遍历。

  • 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级

    1. var minDepth = function(root) {
    2.   if(!root) return 0
    4.   // 采用广度优先遍历。采用元组方式来记录层级
    5.   const queue =[[root, 1]]
    7.   while(queue.length) {
    8.       let [current, level] = queue.shift()  // 栈头
    10.       if(!current.left && !current.right) return level  // 判断是叶子节点，则直接返回
    11.       if(current.right) queue.push([current.right, level + 1])
    12.       if(current.left) queue.push([current.left, level + 1])
    13.   }
    14. };

    时间复杂度是 O(N)，空间复杂度也是 O(N)。

三、路径总和

题目(LT112. 路径总和)
给定二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

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

示例 1：
image.png

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

示例 2：
image.png

输入：root = [1,2,3], targetSum = 5 输出：false

示例 3：

输入：root = [1,2], targetSum = 0 输出：false

解题思路

  • 在深度优先遍历的过程中，记录当前路径的节点值的和。

  • 在叶子节点处，判断当前路径的节点值得和是否等于目标值

    1. var hasPathSum = function(root, targetSum) {
    2.   if(!root) return false
    3.   let result = false
    5.   const dfs = (root, sum)=> {
    6.         // 只有在叶子节点处才会进行判断。
    7.       if(!root.left && !root.right && sum === targetSum) {
    8.           result = true
    9.       }
    11.       if(root.left) dfs(root.left, sum + root.left.val)
    12.       if(root.right) dfs(root.right, sum + root.right.val)
    13.   }
    15.   dfs(root, root.val)
    16.   return result
    17. };

    时间复杂度是O(N)。由于使用了递归，递归会使用函数调用堆栈，所以空间复杂度也是O(N)。