8.2 二叉树的深度优先搜素

二叉树的深度优先搜索可分为:

• 前序遍历
• 中序遍历
• 后序遍历

8.2.1 前序遍历

前序遍历顺序:

1. 根节点
2. 左子树
3. 右子树

递归

func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    dfsPreorderRecursively(root, &res)
    return res
}

func dfsPreorderRecursively(root *TreeNode, res *[]int) {
    if root != nil {
        *res = append(*res, root.Val)
        dfsPreorderRecursively(root.Left, res)
        dfsPreorderRecursively(root.Right, res)
    }
}

迭代

func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    // 栈
    st := make([]*TreeNode, 0)
    // 当前遍历节点
    cur := root
    for cur != nil || len(st) > 0 {
        for cur != nil {
            // 根
            res = append(res, cur.Val)
            // 左子树
            st = append(st, cur)
            cur = cur.Left
        }
        // 右子树
        cur = st[len(st)-1]
        st = st[0 : len(st)-1]
        cur = cur.Right
    }

    return res
}

8.2.2 中序遍历

中序遍历的顺序:

1. 左子树
2. 根节点
3. 右子树

递归

优点: 代码逻辑简单

缺点:

1. 若二叉树深度过大, 则会导致栈溢出
2. 代码太简单

func inorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	dfsInorderRecursively(root, &res)
	return res
}

func dfsInorderRecursively(root *TreeNode, res *[]int) {
	if root != nil {
		dfsInorderRecursively(root.Left, res)
		*res = append(*res, root.Val)
		dfsInorderRecursively(root.Right, res)
	}
}

迭代

基于栈的后进先出的规则进行迭代.

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    
    // 栈
    st := make([]*TreeNode, 0)
    // 当前节点
    cur := root
    for cur != nil || len(st) != 0 {
        // 左子树
        for cur != nil {
            st = append(st, cur)
            cur = cur.Left
        }
        // 根
        cur = st[len(st)-1]
        st = st[0:len(st)-1]
        res = append(res, cur.Val)
        // 右子树
        cur = cur.Right
    }

    return res
}

8.2.3 后序遍历

后序遍历顺序:

1. 左子树
2. 右子树
3. 根节点

递归

func postorderTraversalWithRecursion(root *TreeNode) []int {
	res := make([]int, 0)
	dfsInorderRecursively(root, &res)
	return res
}

func dfsPostorderRecursively(root *TreeNode, res *[]int) {
	if root != nil {
		dfsInorderRecursively(root.Left, res)
		dfsInorderRecursively(root.Right, res)
		*res = append(*res, root.Val)
	}
}

迭代

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    // stack
    st := make([]*TreeNode, 0)
    // current node
    cur := root
    // previous node
    var prev *TreeNode
    for cur != nil || len(st) > 0 {
        // left tree
        for cur != nil {
            st = append(st, cur)
            cur = cur.Left
        }
        cur = st[len(st)-1]
        if cur.Right != nil && cur.Right != prev {
            // right tree
            cur = cur.Right
        } else {
            // root
            res = append(res, cur.Val)
            st = st[: len(st)-1]
            prev = cur
            cur = nil
        }
    }

    return res
}

8.2.4 问题47: 二叉树剪枝

LCR 047. 二叉树剪枝

给定一个二叉树 根节点 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

8.2.4.1 分析&题解

如果要删除一个全是0的子树, 就需要判断左子树和右子树以及当前节点是否全为0.

这个顺序和后序遍历相同, 那么可以使用后序遍历的递归来解决.

func pruneTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    // 剪除左子树
    root.Left = pruneTree(root.Left)
    // 剪除右子树
    root.Right = pruneTree(root.Right)
    // 剪除当前树
    if root.Left == nil && root.Right == nil && root.Val == 0 {
        return nil
    }

    return root
}

8.2.5 问题48: 序列化和反序列化二叉树

LCR 048. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例 1：

img

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

• 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，也可以采用其他的方法解决这个问题。
• 树中结点数在范围 [0, 10^4] 内
• -1000 <= Node.val <= 1000

8.2.5.1 分析&题解

使用前序遍历来进行序列化和反序列化.

序列化: 使用前序遍历递归, 将数值和nil转化成字符串, 使用逗号,拼接

反序列化: 使用前序遍历递归, 将字符串转化成二叉树

type Codec struct {
    
}

func Constructor() Codec {
     return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    var f func(*TreeNode) string
    f = func(node *TreeNode) string {
      var sb strings.Builder
      // 递归出口
      if node == nil {
        return "null"
      }
      // root 
      rootStr := strconv.Itoa(node.Val)
      // left 
      leftStr := f(node.Left)
      // right 
      rightStr := f(node.Right)

      sb.WriteString(rootStr)
      sb.WriteByte(',')
      sb.WriteString(leftStr)
      sb.WriteByte(',')
      sb.WriteString(rightStr)

      return sb.String()
    }
    return f(root)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    strs := strings.Split(data, ",")
    return dfs(&strs)
}

func dfs(strs *[]string) *TreeNode {
  if len(*strs) == 0 {
    return nil
  }
  // node val
  str := (*strs)[0]
  *strs =(*strs)[1:]
  if str == "null" {
    return nil
  }

  val, _ := strconv.Atoi(str)
  // root node
  root := &TreeNode{Val: val}
  // left tree
  root.Left = dfs(strs)
  // right tree
  root.Right = dfs(strs)

  return root
}

可以在函数内使用匿名递归函数.

8.2.6 问题49: 从根节点到叶节点的路径数字之和

LCR 049. 求根节点到叶节点数字之和

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

示例 1：

img

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

img

输入：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

8.2.6 分析&题解

路径问题一般使用深度优先搜索, 此问题使用前序遍历.

对于当前路径表示的数字 path, 下一路径所表示的数字可以由公式 path = path*10 + nodeVal .

func sumNumbers(root *TreeNode) int {
    // 递归
    return dfs(root, 0)
}

func dfs(root *TreeNode, path int) int {
    // 递归出口
    if root == nil {
        return 0
    }

    path = path*10 + root.Val
    // 叶节点
    if root.Left == nil && root.Right == nil {
        return path
    }

    return dfs(root.Left, path) + dfs(root.Right, path)
}

8.2.7 问题50: 向下路径点之和

LCR 050. 路径总和 III

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

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

示例 1：

img

输入：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]
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000

8.2.7.1 分析&题解

此问题实际上是路径和与两数之和的复合问题. 需要使用前序遍历和哈希表来解决.

流程:

1. 构建哈希表(路径和, 出现次数); 初始值 (0, 1)
2. 进行前序遍历:
   1. 当前路径中, path-sum 出现的次数;
   2. 左子树路径中出现的次数
   3. 右子树路径中出现的次数
3. 总次数为三条路径次数之和

func pathSum(root *TreeNode, targetSum int) int {
	m := make(map[int]int)
	// 初始值
	m[0] = 1
	return dfs(root, m, targetSum, 0)
}

func dfs(root *TreeNode, m map[int]int, sum, path int) int {
	// 递归出口
	if root == nil {
		return 0
	}
	// 当前路径和
	path += root.Val
	// 寻找目标路径个数
	cnt := 0
	if v, ok := m[path-sum]; ok {
		cnt = v
	}

	// 记录次数
	m[path]++

	// 左右子树
	cnt += dfs(root.Left, m, sum, path)
	cnt += dfs(root.Right, m, sum, path)
	
	// 去除已经统计的路径
	m[path]--
	
	return cnt
}

8.2.8 问题51: 节点之和的最大路径

LCR 051. 二叉树中的最大路径和

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

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

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

示例 1：

img

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

示例 2：

img

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

提示：

• 树中节点数目范围是 [1, 3 * 10^4]
• -1000 <= Node.val <= 1000

8.2.8.1 分析&题解

路径可能经过左子树或右子树而不经过根节点, 那么先求出左右子树的路径之和, 再求经过根节点的路径之和, 三者中最大的就是树中最大的路径和.

先左右子树再根节点, 所以采用后序遍历解决.

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt
	// 递归函数
	var dfs func(*TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 计算左右子树最大路径和
		leftMax := max(dfs(node.Left), 0)
		rightMax := max(dfs(node.Right), 0)

		// 当前路径和
		path := node.Val + leftMax + rightMax

		// 更新最大
		maxSum = max(maxSum, path)

		return node.Val + max(leftMax, rightMax)
	}
	dfs(root)

	return maxSum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Reference

1. 剑指Offer（专项突破版）