一、二叉树的层序遍历

题目(LT102. 二叉树的层序遍历)
给你一个二叉树，请你返回其按 层序遍历 得到的节点值(即逐层地，从左到右访问所有节点)。

示例：
二叉树：[3,9,20,null,null,15,7],

  1. 3

/ \ 9 20 / \ 15 7

返回其层序遍历结果：

[ [3], [9,20], [15,7] ]

解题思路

  • 层序遍历顺序就是广度优先遍历；
  • 不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同数组中。

方案一

  1. var levelOrder = function(root) {
  2.     if(!root) return []
  4.     const stack = [[root,0]] // 采用原数组方式，1代表层级
  5.     const result = []
  7.     while(stack.length){
  8.         const [node, level] = stack.shift()
  9.         if(result[level]) {
  10.             result[level].push(node.val)
  11.         } else {
  12.             result[level] = [node.val]
  13.         }
  15.         if(node.left) stack.push([node.left, level + 1])
  16.         if(node.right) stack.push([node.right, level + 1])
  17.     }
  19.     return result
  20. };

方案二
广度优先遍历在不断地将老节点出队，并且在不断地将老节点的孩子入队。如果我们能保证在每次的while循环迭代里，都能把所有的老人都出队，并把下一层级的所有节点都入队的话，就可以确保while循环体内刚进来的时候队列里都是同一层级的节点。

  1. var levelOrder = function(root) {
  2.     if(!root) return []
  4.     const stack = [root]
  5.     const result = []
  7.     while(stack.length){  // 每次遍历是对层级做遍历
  8.         let length = stack.length
  9.         result.push([])
  11.           // 将同一层级的所有节点都推到这个数组里
  12.         while(length--) {
  13.             const node = stack.shift()
  15.             result[result.length - 1].push(node.val)  // 利用数组自身长度来处理层级
  17.             if(node.left) stack.push(node.left)
  18.             if(node.right) stack.push(node.right)
  19.         }
  20.     }
  22.     return result
  23. };

因为是广度优先遍历，时间复杂度是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)。