二叉树的深度优先

lc124. 二叉树的最大路径困难hot

题目描述

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

思路

使用递归，因为树每次只能进入一侧，所以每一轮贡献的值只能是当前根节点+左边节点或根节点+右节点和0之间的最大值,记为max并返回

因为有可能是root -> root.left -> root.right组成的值比 root.root -> root -> root.left/right还要大，记为sum，然后更新到全局变量中

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
  // 设置一个全局最小的和
  let sum = Number.MIN_SAFE_INTEGER
  const dfs = node => {
    if(!node) return 0
    const left = dfs(node.left)
    const right = dfs(node.right)
    // 算出路径最大的和，替换全局的sum
    sum = Math.max(sum, left + node.val + right)
    // 返回每一轮最大的值
    const max = Math.max(left, right) + node.val
    return max > 0 ? max : 0
  }
  dfs(root)
  return sum
};

• 时间复杂度： O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2次。
• 空间复杂度： O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

lc543. 二叉树的直径简单hot

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :

给定二叉树
          1
         / \
        2   3
       / \     
      4   5 
      
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]

注意：两结点之间的路径长度是以它们之间边的数目表示。

var diameterOfBinaryTree = function(root) {
  let res = 0
  const depth = node => {
    if(!node) return 0
    const left = depth(node.left)
    const right = depth(node.right)
    // 计算最大直径 更新到全局res上
    res = Math.max(res, left + right)
    // 每轮返回左子树和右子树中的最大值
    return Math.max(left, right) + 1
  }
  depth(root)
  return res
};

时间复杂度O(n)

空间复杂度O(h) h为二叉树的最大深度，是一个常数变量

lc257. 二叉树的所有路径简单

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

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

var binaryTreePaths = function(root) {
  if(!root) return []
  const res = []

  const binary = (node, str) => {
    if(!node.left && !node.right) {
      str += node.val
      res.push(str)
      return
    }

    str += `${node.val}->`
    if(node.left) binary(node.left, str)
    if(node.right) binary(node.right, str)
  }

  binary(root, '')
  return res
};

• 时间复杂度：O(N)，其中 N 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N)；
• 空间复杂度：O(N)，其中 N 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 N，此时每一层的 path 变量的空间代价的总和的空间复杂度为 O(N)，最好情况下，当二叉树为平衡二叉树时，它的高度为 logN，此时空间复杂度为O((logN)2)。

lc98. 验证二叉搜索树中等hot

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]

输出：true

示例 2：

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

输出：false

解释：根节点的值是 5 ，但是右子节点的值是 4 。

var isValidBST = function(root) {
  const dfs = (root, minVal, maxVal) => {
    if(!root) return true

    if(root.val <= minVal || root.val >= maxVal) return false

    return dfs(root.left, minVal, root.val) && dfs(root.right, root.val, maxVal)
  }

  return dfs(root, -Infinity, +Infinity)
};

• 时间复杂度 : O(n)，其中 n为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
• 空间复杂度 : O(n)，其中 n为二叉树的节点个数。栈最多存储 n个节点，因此需要额外的 O(n)的空间。