1. 树的简介

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；
树、广度优先、深度优先 - 图1
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
image.png

二叉树的深度：
某节点的深度是指从根节点到该节点的最长简单路径边的条数。(从上往下数)

二叉树的高度：
指从该节点到叶子节点的最长简单路径边的条数。（从下往上数）

注意：这里边的条数是规定根节点的深度和叶子节点的高度是0；
所以树的深度和高度是相等的，而对其他节点来说深度和高度不一定相等。
树、广度优先、深度优先 - 图3

如 B和C节点深度都为1，因为从根节点到到该节点的边数为1，B的高度为2，而C的高度为1。
当然树的深度是3高度也是3。树的高度和深度是相等的。

2. 树、广度优先、深度优先的一些常用模板

二叉树的前序遍历：

  1. func preorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}                
  3.     var preOrder func(*TreeNode)        //定义匿名函数，好处是不需要将ans的指针递归传递
  4.     preOrder = func(node *TreeNode){
  5.         if node == nil{                    //终止条件
  6.             return 
  7.         }
  8.         ans = append(ans,node.Val)        //处理逻辑
  9.         preOrder(node.Left)                
  10.         preOrder(node.Right)
  11.     }
  12.     preOrder(root)
  13.     return ans    
  14. }

二叉树的中序遍历：

  1. func inorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}                
  3.     var inOrder func(*TreeNode)            //定义匿名函数，好处是不需要将ans的指针递归传递
  4.     inOrder = func(node *TreeNode){
  5.         if node == nil{                    //终止条件
  6.             return 
  7.         }
  8.         inOrder(node.Left)        
  9.         ans = append(ans,node.Val)        //处理逻辑        
  10.         inOrder(node.Right)
  11.     }
  12.     inOrder(root)
  13.     return ans  
  14. }

二叉树的后序遍历：

  1. func postorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}                
  3.     var postOrder func(*TreeNode)        //定义匿名函数，好处是不需要将ans的指针递归传递
  4.     postOrder = func(node *TreeNode){
  5.         if node == nil{                    //终止条件
  6.             return 
  7.         }
  8.         postOrder(node.Left)        
  9.         postOrder(node.Right)
  10.         ans = append(ans,node.Val)        //处理逻辑        
  11.     }
  12.     postOrder(root)
  13.     return ans  
  14. }

深度优先：

  1. func preorderTraversal(root *TreeNode) []int {
  2.     ans := []int{}                
  3.     var preOrder func(*TreeNode)        //定义匿名函数，好处是不需要将ans的指针递归传递
  4.     preOrder = func(node *TreeNode){
  5.         if node == nil{                    //终止条件
  6.             return 
  7.         }
  8.         ans = append(ans,node.Val)        //处理逻辑
  9.         preOrder(node.Left)                
  10.         preOrder(node.Right)
  11.     }
  12.     preOrder(root)
  13.     return ans    
  14. }
  15. //前序遍历是深度优先的一种，通常使用前序遍历作为dfs的模板

广度优先：

  1. func levelOrder(root *TreeNode) [][]int {
  3.     queue := []*TreeNode{root}
  5.     for len(queue) > 0{
  6.         size := len(queue)
  7.         for i:=0;i<size;i++{                         //for循环内的元素都在同一深度
  8.             node := queue[i]
  9.             if node.Left != nil{
  10.                 queue = append(queue,node.Left)
  11.             }
  12.             if node.Right != nil{
  13.                 queue = append(queue,node.Right)
  14.             }
  15.             fmt.Println(node.Val)
  16.         }
  17.         queue = queue[size:]
  18.     }
  19.     return [][]int{}
  20. }

3.二叉树的广度优先题目

102. 二叉树的层序遍历 中等

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

题解概要：

经典题目，直接套用bfs的模板即可。

代码：

  1. func levelOrder(root *TreeNode) [][]int {
  2.     if root == nil{
  3.         return [][]int{}
  4.     }
  5.     queue := []*TreeNode{root}
  6.     ans := [][]int{}
  8.     for len(queue) > 0 {
  9.         size := len(queue)
  10.         temp := []int{}
  11.         for i := 0 ;i<size;i++{
  12.             node := queue[i]
  13.             if node.Left != nil {
  14.                 queue = append(queue,node.Left)
  15.             }
  16.             if node.Right != nil {
  17.                 queue = append(queue,node.Right)
  18.             }
  19.             temp = append(temp,node.Val)
  20.         }
  21.         queue = queue[size:]
  22.         ans = append(ans,temp)
  23.     }
  24.     return ans
  25. }

662. 二叉树最大宽度 中等

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:
输入: 

  1.        1<br />         /   \<br />        3     2<br />       / \     \  <br />      5   3     9

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:
输入: 

  1.       1<br />         /  <br />        3    <br />       / \       <br />      5   3

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:
输入: 

  1.       1<br />         / \<br />        3   2 <br />       /        <br />      5

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:
输入: 

  1.       1<br />         / \<br />        3   2<br />       /     \  <br />      5       9 <br />     /         \<br />    6           7<br />输出: 8<br />解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。<br />注意: 答案在32位有符号整数的表示范围内

题解概要：

1.每一行的宽度等于 最右侧节点的编号-最左侧节点的编号+1。
2.因此还需要一个队列用于记录节点的编号。

代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func widthOfBinaryTree(root *TreeNode) int {
  11.     if root == nil{
  12.         return 0
  13.     }
  15.     ans := 0
  16.     queue := []*TreeNode{root}
  17.     position := []int{1}
  19.     for len(queue) > 0{
  20.         size := len(queue)
  21.         first,last := 0,0
  22.         for i := 0;i < size;i++{
  23.             node := queue[i]
  24.             pos := position[i]
  25.             if i == 0{
  26.                 first = pos
  27.             }
  28.             if i == size - 1{
  29.                 last = pos
  30.             }
  31.             if first != 0 && last != 0{
  32.                 ans = max(ans,last - first + 1)
  33.             }
  34.             if node.Left != nil{
  35.                 queue = append(queue,node.Left)
  36.                 position = append(position,pos*2)
  37.             }
  38.             if node.Right != nil{
  39.                 queue = append(queue,node.Right)
  40.                 position = append(position,pos*2+1)
  41.             }
  42.         }
  43.         queue = queue[size:]
  44.         position = position[size:]
  45.     }
  46.     return ans
  47. }
  50. func max(a,b int)int{
  51.     if a > b{
  52.         return a
  53.     }
  54.     return b
  55. }

广度优先较为简单，套用模板根据题意修改一些逻辑即可。相关题目如下：

103. 二叉树的锯齿形层序遍历

199. 二叉树的右视图

226. 翻转二叉树

104. 二叉树的最大深度

116. 填充每个节点的下一个右侧节点指针

111. 二叉树的最小深度

面试题 04.03. 特定深度节点链表

515. 在每个树行中找最大值

101. 对称二叉树

100. 相同的树

993. 二叉树的堂兄弟节点

690. 员工的重要性

4.二叉搜索树相关题目

98. 验证二叉搜索树 中等

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

有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

树、广度优先、深度优先 - 图4
输入：root = [2,1,3]
输出：true

示例 2：
树、广度优先、深度优先 - 图5

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

题解概要：

1.利用二叉搜索树的性质，中序遍历是单调递增的。

代码：

  1.  import "math"
  2. func isValidBST(root *TreeNode) bool {
  4.     pre := math.MinInt64            //这里一定要使用MinInt64，使用MinInt32会有BUG
  6.     var dfs func(*TreeNode)bool
  8.     dfs = func(node *TreeNode)bool{
  10.         if node == nil {            //递归的本质是找到子问题，从子问题推到全局。
  11.             return true
  12.         }
  13.         left  := dfs(node.Left)
  14.         if pre >= node.Val{
  15.             return false
  16.         }
  17.         pre = node.Val
  18.         right := dfs(node.Right)
  19.         return left && right
  20.     }
  22.     return dfs(root)
  23. }

897. 递增顺序搜索树 简单

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：
树、广度优先、深度优先 - 图6
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：
树、广度优先、深度优先 - 图7
输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：
树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

题解概要：

1.利用二叉搜索树的性质，中序遍历是单调递增的。

代码：

  1. func increasingBST(root *TreeNode) *TreeNode {
  2.     head := &TreeNode{}
  3.     cur  := head
  4.     var dfs func(*TreeNode)
  5.     dfs = func(node *TreeNode){
  6.         if node == nil {
  7.             return 
  8.         }
  9.         dfs(node.Left)
  10.         cur.Right = node
  11.         node.Left  = nil      //一定是node.Left等于nil，这样就不会超时
  12.         cur = node
  13.         dfs(node.Right)
  14.     }
  15.     dfs(root)
  16.     return head.Right
  17. }

99. 恢复二叉搜索树 中等

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：
树、广度优先、深度优先 - 图8
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
树、广度优先、深度优先 - 图9
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：
树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

题解概要：

这道题难点，是找到那两个交换节点，把它交换过来就行了。

这里我们二叉树搜索树的中序遍历(中序遍历遍历元素是递增的)

如下图所示，中序遍历顺序是 4,2,3,1，我们只要找到节点 4 和节点 1 交换顺序即可！

这里我们有个规律发现这两个节点：
第一个节点，是第一个按照中序遍历时候前一个节点大于后一个节点，我们选取前一个节点，这里指节点 4；

第二个节点，是在第一个节点找到之后，后面出现前一个节点大于后一个节点，我们选择后一个节点，这里指节点 1；
树、广度优先、深度优先 - 图10
注意：有两种情况需要考虑。1.两个节点不相邻 2.两个节点相邻。

代码：

  1.  import "math"
  2. func recoverTree(root *TreeNode)  {
  3.     pre := &TreeNode{Val:math.MinInt64} //最小值。
  4.     var p *TreeNode  //第一个节点
  5.     var q *TreeNode  //第二个节点
  7.     var dfs func(*TreeNode)
  8.     dfs = func(node *TreeNode){
  9.         if node == nil {
  10.             return 
  11.         }
  12.         dfs(node.Left)
  14.         if p == nil && pre.Val > node.Val{
  15.             p = pre
  16.         }
  17.         if p != nil && pre.Val > node.Val{   //一定要判断这个,表达式不能写错.
  18.             q = node
  19.         }
  20.         pre = node
  21.         dfs(node.Right)
  22.     }
  23.     dfs(root)
  25.     //交换节点的值
  26.     tmp := p.Val
  27.     p.Val = q.Val
  28.     q.Val = tmp
  30. }

相关题目如下：

938. 二叉搜索树的范围和

108. 将有序数组转换为二叉搜索树

230. 二叉搜索树中第K小的元素

剑指 Offer 54. 二叉搜索树的第k大节点

面试题 04.05. 合法二叉搜索树

538. 把二叉搜索树转换为累加树

783. 二叉搜索树节点最小距离

总结：二叉搜索树两个重要的规律：1.中序遍历 2.中序遍历的倒序。
其中，中序遍历时二叉树元素会递增排序；（左根右）
中序遍历的倒序会递减排序。（右根左）

5.二叉树路径题目

543. 二叉树的直径 简单

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

示例 :
给定二叉树

  1.       1<br />         / \<br />        2   3<br />       / \     <br />      4   5    <br />返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。<br />注意：两结点之间的路径长度是以它们之间边的数目表示。

题解概要：

重要的是转化为子问题，以某一节点为根节点的直径最大值等于左子树路径最大值+右子树路径最大值。

代码：

  1. func diameterOfBinaryTree(root *TreeNode) int {
  2.     ans := 0
  3.     var dfs func(*TreeNode)int
  4.     dfs = func(node *TreeNode)int{
  5.         if node == nil {
  6.             return 0
  7.         }
  8.         left := dfs(node.Left)
  9.         right := dfs(node.Right)
  10.         ans = max(ans,left+right)    
  11.         return max(right,left)+1    //返回左右子树路径最大值
  12.     }
  13.     dfs(root)
  14.    return ans
  15.  }
  18.  func max(a int,b int)int{
  19.      if a > b {
  20.          return a
  21.      }
  22.      return b
  23.  }

剑指 Offer 34. 二叉树中和为某一值的路径 中等

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 target = 22，

  1.           5<br />             / \<br />            4   8<br />           /   / \<br />          11  13  4<br />         /  \    / \<br />        7    2  5   1<br />返回:

[
[5,4,11,2],
[5,8,4,5]
]

提示：
节点总数 <= 10000

题解概要：

1.在递归时，使用两个变量分别记录路径和与路径上所有元素的值。
2.判断某个节点是否为叶子节点，需同时满足 node.Left == nil && node.Right ==nil
3.使用切片做参数传递时，注意传递的是指针，所以需要做一次拷贝。

代码：

  1. func pathSum(root *TreeNode, target int) [][]int {
  3.     ans := [][]int{}
  5.     var dfs func(*TreeNode,[]int,int)
  6.     dfs = func(node *TreeNode,sums []int,sum int){
  8.         if node == nil {
  9.             return
  10.         }
  11.         //这里要拷贝一次,不然后面的递归会污染前面的值
  12.         sumsCopy := make([]int,len(sums))
  13.         copy(sumsCopy,sums)                      
  14.         sumsCopy = append(sumsCopy,node.Val)    
  15.         sum += node.Val
  16.         if node.Left == nil && node.Right == nil && sum == target{
  17.             ans = append(ans,sumsCopy)
  18.         }
  19.         dfs(node.Left,sumsCopy,sum)
  20.         dfs(node.Right,sumsCopy,sum)
  21.     }
  22.     dfs(root,[]int{},0)
  23.     return ans
  24. }

129. 求根节点到叶节点数字之和 中等

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

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

示例 1：
树、广度优先、深度优先 - 图11
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：
树、广度优先、深度优先 - 图12
输入：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

题解概要：

这道题与剑指 Offer 34. 二叉树中和为某一值的路径思路相同。

代码：

  1. func sumNumbers(root *TreeNode) int {
  3.     ans := 0
  5.     var dfs func(*TreeNode, int)
  6.     dfs = func(node *TreeNode,num int){
  7.         if node == nil{
  8.             return 
  9.         }
  10.         num = num*10 + node.Val        //常用的表达多位数的一种写法。
  12.         if node.Left == nil && node.Right == nil{
  13.             ans += num 
  14.         }
  15.         dfs(node.Left,num)
  16.         dfs(node.Right,num)
  17.     }
  18.     dfs(root,0)
  19.     return ans
  20. }

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

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

示例 1：
树、广度优先、深度优先 - 图13
输入：root = [1,2,3,null,5]
输出：[“1->2->5”,”1->3”]

示例 2：
输入：root = [1]
输出：[“1”]

提示：
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

题解概要：

这道题与剑指 Offer 34. 二叉树中和为某一值的路径思路相同。

代码：

  1. func binaryTreePaths(root *TreeNode) []string {
  2.     ans := []string{}
  3.     var dfs func(*TreeNode,string)
  4.     dfs = func(node *TreeNode,path string){
  5.         if node == nil{
  6.             return
  7.         }
  8.         path += strconv.Itoa(node.Val)            //这道题无法使用 []byte，->符号不是ASCI码
  9.         if node.Left == nil && node.Right == nil{
  10.             ans = append(ans,path)
  11.         }
  12.         path += "->"
  13.         dfs(node.Left,path)
  14.         dfs(node.Right,path)
  15.     }
  16.     dfs(root,"")
  17.     return ans
  18. }

437. 路径总和 III 中等

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：
树、广度优先、深度优先 - 图14
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

题解概要：

本题使用前缀和，大佬题解如下：
https://leetcode-cn.com/problems/path-sum-iii/solution/qian-zhui-he-di-gui-hui-su-by-shi-huo-de-xia-tian/
https://leetcode-cn.com/problems/path-sum-iii/solution/dui-qian-zhui-he-jie-fa-de-yi-dian-jie-s-dey6/

代码：

  1. func pathSum(root *TreeNode, targetSum int) int {
  3.     ans := 0 
  5.     preSum := map[int]int{0:1} //一定要有初始值，不然有问题
  7.     var dfs func(*TreeNode,int)
  9.     dfs = func(node *TreeNode,sum int){
  10.         if node == nil{
  11.             return
  12.         }
  13.         sum += node.Val
  14.         if count,ok := preSum[sum-targetSum];ok{
  15.             ans += count            //判断前缀和map是否存在
  16.         }    
  17.         preSum[sum] ++ 
  18.         dfs(node.Left,sum)
  19.         dfs(node.Right,sum)
  20.         preSum[sum]--              //遍历完子树需要清除当前节点的值
  21.     }
  22.     dfs(root,0)
  23.     return ans
  24. }

687. 最长同值路径 中等

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。

示例 1:
树、广度优先、深度优先 - 图15
输入：root = [5,4,5,1,1,5]
输出：2

示例 2:
树、广度优先、深度优先 - 图16
输入：root = [1,4,5,4,4,5]
输出：2

提示:
树的节点数的范围是 [0, 104]
-1000 <= Node.val <= 1000
树的深度将不超过 1000

题解概要：

套用dfs模板，本题最重要的是如何界定当前路径的每个节点都是相同的。

代码：

  1. func longestUnivaluePath(root *TreeNode) int {
  2.     ans := 0
  3.     var dfs func(*TreeNode)int
  4.     dfs = func(node *TreeNode)int{
  5.         if node == nil{
  6.             return 0
  7.         }
  8.         left := dfs(node.Left)    
  9.         right := dfs(node.Right)    
  10.         leftLen,rightLen := 0,0
  11.         if node.Left != nil && node.Left.Val == node.Val{
  12.             leftLen = left+1        //路径是否相同
  13.         }
  14.         if node.Right != nil && node.Right.Val == node.Val{
  15.             rightLen = right + 1    //路径是否相同
  16.         }
  17.         ans = max(ans,leftLen+rightLen)
  18.         return max(leftLen,rightLen)
  19.     }
  20.     dfs(root)
  21.     return ans
  22. }
  24. func max(a int,b int)int{
  25.     if a > b {
  26.         return a
  27.     }
  28.     return b
  29. }

124. 二叉树中的最大路径和 困难

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
树、广度优先、深度优先 - 图17

示例 2：
树、广度优先、深度优先 - 图18
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

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

题解概要：

1.分解成子问题，先求左右子树的路径最大和。
2.再求经过某个节点的路径最大和。
3.由于node.Val可能为负数，因此要左右路径最大和要与0进行比较。只有大于0的路径才有贡献。

代码：

  1.  import "math"
  2. func maxPathSum(root *TreeNode) int {
  3.     ans := math.MinInt32
  5.     var dfs func(*TreeNode)int
  6.     dfs = func(node *TreeNode)int{
  7.         if node == nil{
  8.             return  0
  9.         }
  10.         //子最大路径和要与0进行比较,只有大于0时才有贡献，否则就只返回节点的值
  11.         left := max(dfs(node.Left),0)    
  12.         right := max(dfs(node.Right),0)
  14.         //更新最大路径和
  15.         ans = max(ans,left+right+node.Val)
  17.         return node.Val + max(left,right)
  18.     }
  20.     dfs(root)
  21.     return ans
  22. }
  24. func max(a int,b int)int{
  25.     if a > b{
  26.         return a
  27.     }
  28.     return b
  29. }

6.二叉树的其他题目

872. 叶子相似的树 简单

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例 1：
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

示例 2：
输入：root1 = [1], root2 = [1]
输出：true

示例 3：
输入：root1 = [1], root2 = [2]
输出：false

示例 4：
输入：root1 = [1,2], root2 = [2,2]
输出：true

示例 5：
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

提示：
给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。

题解概要：

套用dfs模板，分别找到叶子之和，但要需要传递指针，要记得如何传递指针

代码：

  1. func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
  3.     ans1 := []int{}
  4.     ans2 := []int{}
  5.     var dfs func(*TreeNode,*[]int)
  6.     dfs = func(node *TreeNode,ans *[]int){
  7.         if node == nil{
  8.             return
  9.         }
  10.         if node.Left == nil && node.Right == nil{
  11.             *ans = append(*ans,node.Val)
  12.             return
  13.         }
  14.         dfs(node.Left,ans)
  15.         dfs(node.Right,ans)
  16.     }
  17.     dfs(root1,&ans1)
  18.     dfs(root2,&ans2)
  19.     return isSimilar(ans1,ans2)
  20. }
  22. func isSimilar(ans1 []int,ans2 []int)bool{
  23.     if len(ans1) != len(ans2){
  24.         return false
  25.     }
  26.     for i,_ := range ans1{
  27.         if ans1[i] != ans2[i]{
  28.             return false
  29.         }
  30.     }
  31.     return true
  32. }

404. 左叶子之和 简单

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：
树、广度优先、深度优先 - 图19
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:
输入: root = [1]
输出: 0

提示:
节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

题解概要：

套用dfs模板，关键是如何找到左叶子。

代码：

  1. func sumOfLeftLeaves(root *TreeNode) int {
  2.     ans := 0
  3.     var dfs func(*TreeNode)
  4.     dfs = func(node *TreeNode){
  5.         if node == nil{
  6.             return
  7.         }
  8.         //找到左叶子节点
  9.         if node.Left != nil && node.Left.Left == nil && node.Left.Right == nil{
  10.             ans += node.Left.Val
  11.         }
  12.         dfs(node.Left)
  13.         dfs(node.Right)
  14.     }
  15.     dfs(root)
  16.     return ans
  17. }

617. 合并二叉树 简单

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：
树、广度优先、深度优先 - 图20
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：
两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

题解概要：

对于某个节点的合并一共有三种情况。
树1节点为空，则使用树2节点。
树2节点为空，则使用树1节点。
树1、树2节点都不为空，将两者的值相加。

代码：

  1. func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
  3.     var dfs func(*TreeNode,*TreeNode)*TreeNode  
  5.     dfs = func(node1 *TreeNode,node2 *TreeNode)*TreeNode{
  6.         if node1  == nil{
  7.             return node2 
  8.         }
  9.         if node2 == nil{
  10.             return node1
  11.         }
  12.         node1.Val += node2.Val
  13.         node1.Left = dfs(node1.Left,node2.Left)
  14.         node1.Right = dfs(node1.Right,node2.Right)
  15.         return node1
  16.     }
  17.     return dfs(root1,root2)
  18. }

110. 平衡二叉树 简单

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：
树、广度优先、深度优先 - 图21
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
树、广度优先、深度优先 - 图22
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true

提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

题解概要：

求高度，则使用dfs模板，根据题意可得结果。

代码：

  1. func isBalanced(root *TreeNode) bool {
  3.     flag := true
  4.     var dfs func(*TreeNode) int
  6.     dfs = func(node *TreeNode)int{
  8.         if node == nil{
  9.             return 0
  10.         }
  12.         left := dfs(node.Left)
  13.         right := dfs(node.Right)
  15.         if abs(left-right) > 1{    //只要其中的一个子树不满足条件，就不是平衡高度二叉树
  16.             flag = false
  17.         }
  19.         return max(left,right)+1
  20.     }
  21.     dfs(root)
  22.     return flag
  23. }
  25. func max(a int,b int)int{
  26.     if  a > b {
  27.         return a
  28.     }
  29.     return b
  30. }
  32. func abs(a int)int{
  33.     if a < 0 {
  34.         return -a
  35.     }   
  36.     return a
  37. }

剑指 Offer 26. 树的子结构 中等

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

  1.  3<br />    / \<br />   4   5<br />  / \<br /> 1   2<br />给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：
0 <= 节点个数 <= 10000

题解概要：

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/
1.如果B是A的子结构，要么B和A相同，要么B是A左子树上的一段，要么B是A右子树上的一段。
2.判断两个树相同的条件是：A的左子树和B的左子树相同，A的右子树和B的右子树相同，并且A的值和B的值相等

代码：

  1.  */
  2. func isSubStructure(A *TreeNode, B *TreeNode) bool {
  4.     if A == nil || B == nil {
  5.         return false
  6.     }
  7.     return dfs(A,B) || isSubStructure(A.Left,B) || isSubStructure(A.Right,B) 
  8. }
  10. func dfs (A *TreeNode, B *TreeNode)bool{
  12.     if B == nil {
  13.         return true
  14.     }
  15.     if A == nil || A.Val != B.Val{
  16.         return false
  17.     }
  18.     return dfs(A.Left,B.Left) &&  dfs(A.Right,B.Right)
  19. }

236. 二叉树的最近公共祖先 中等

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

题解概要：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/

代码：

  1.  func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  3.      if root == nil  || root.Val == p.Val || root.Val == q.Val{
  4.          return root
  5.      }
  6.      left := lowestCommonAncestor(root.Left,p,q)
  7.      right := lowestCommonAncestor(root.Right,p,q)
  9.     if left != nil && right != nil {  //一共有3种情况。
  10.         return root
  11.     }
  12.     if left == nil{
  13.         return right
  14.     }else{
  15.         return left
  16.     }
  18. }

7.岛屿问题

200. 岛屿数量 中等

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1

示例 2：
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

题解概要：

岛屿问题有统一的模板，可以看一下大佬整理好的模板。
https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

代码：

  1. func numIslands(grid [][]byte) int {
  3.     ans := 0
  5.     for i:= 0;i<len(grid);i++{
  6.         for j:= 0; j<len(grid[i]);j++{
  7.             if grid[i][j] == '1'{
  8.                 dfs(grid,i,j)
  9.                 ans ++
  10.             }
  11.         }
  12.     }
  13.     return ans
  14. }
  16. func dfs(grid [][]byte,r int, c int){
  18.     //判断是否过界
  19.     if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[r]){
  20.         return 
  21.     }
  23.     //判断是否为陆地
  24.     if grid[r][c] != '1'{
  25.         return 
  26.     }  
  28.     //将遍历过的各自设置为2,不进行重复遍历
  29.     grid[r][c] = '2'
  31.     //向四个方向眼神
  32.     dfs(grid,r,c-1)
  33.     dfs(grid,r,c+1)
  34.     dfs(grid,r+1,c)
  35.     dfs(grid,r-1,c)
  37. }

岛屿问题相关题目如下：

剑指 Offer 13. 机器人的运动范围

695. 岛屿的最大面积

463. 岛屿的周长

8.二叉树构建与序列化问题

剑指 Offer 07. 重建二叉树（前序、中序构建二叉树）中等

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
树、广度优先、深度优先 - 图23
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：
0 <= 节点个数 <= 5000

题解概要：

1.通过前序遍历找到根节点
2.通过中序遍历找到左子树节点，剩余的即为右子树节点
3.递归执行

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/jian-dan-li-jie-di-gui-zhong-jian-er-cha-ursl/
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/zhong-jian-er-cha-shu-di-gui-fa-da-bai-9-h5by/

代码：

  1. func buildTree(preorder []int, inorder []int) *TreeNode {
  3.     if len(preorder) == 0 || len(inorder) == 0 || len(preorder) != len(inorder){
  4.         return nil
  5.     }
  7.     posMap := map[int]int{}
  9.     for i,v := range inorder{
  10.         posMap[v] = i
  11.     }
  12.     var build func(int,int,int,int)*TreeNode
  14.     build = func(preLeft int,preRight int,inLeft int,inRight int)*TreeNode{
  16.         //终止条件
  17.         if preLeft > preRight{
  18.             return nil
  19.         }
  20.         //根节点的值
  21.         rootVal := preorder[preLeft]
  22.         //求根节点在中序遍历中的位置
  23.         rootPos := posMap[rootVal]
  24.         //求左子树的长度
  25.         leftNum := rootPos-inLeft
  26.         //创建节点
  27.         node := &TreeNode{Val:rootVal}
  28.         //递归创建左子树
  29.         node.Left = build(preLeft+1,preLeft+leftNum,inLeft,inRight-1)
  30.         //递归创建右
  31.         node.Right = build(preLeft+leftNum+1,preRight,rootPos+1,inRight)
  32.         return node
  33.     }
  34.     return build(0,len(preorder)-1,0,len(inorder)-1)
  35. }

106. 从中序与后序遍历序列构造二叉树（中序、后序构建二叉树）中等

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:
树、广度优先、深度优先 - 图24
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

题解概要：

后序遍历从右往左看就是前序遍历。

代码：

  1.  //后序遍历从右往左看就是前序遍历
  2. func buildTree(inorder []int, postorder []int) *TreeNode {
  4.     if len(inorder) == 0 || len(postorder) == 0 || len(inorder) != len(postorder){
  5.         return nil
  6.     }
  7.     posMap := map[int]int{} //存放中序遍历的值-索引
  8.     for i,v := range inorder{
  9.         posMap[v] = i
  10.     }
  12.     var build func(int,int,int,int) *TreeNode
  13.     build = func(postLeft int,postRight int,inLeft int,inRight int)*TreeNode{
  15.         if postLeft > postRight{
  16.             return nil
  17.         }
  18.         //根节点值
  19.         rootVal := postorder[postRight] 
  20.         //查找根节点在中序遍历中出现的位置
  21.         rootPos := posMap[rootVal]
  22.         //计算右子树的长度
  23.         rightNum := inRight - rootPos
  24.         //创建节点
  25.         node := &TreeNode{Val:rootVal}
  26.         //创建右节点
  27.         node.Right = build(postRight-rightNum,postRight-1,rootPos+1,inRight)
  28.         //创建左节点
  29.         node.Left =  build(postLeft,postRight-rightNum-1,inLeft,rootPos-1)
  30.         return node
  31.     }
  32.     return build(0,len(postorder)-1,0,len(inorder)-1)
  33. }

889. 根据前序和后序遍历构造二叉树中等

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]

提示：
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

题解概要：

前序遍历中第一个节点是根节点，第二个节点是左子树的根节点。

代码：

  1. func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
  3.     posMap := map[int]int{}
  4.     for i,v := range postorder{
  5.         posMap[v] = i
  6.     }
  8.     var build func(int,int,int,int)*TreeNode
  9.     build = func(preLeft int,preRight int,postLeft int,postRight int)*TreeNode{
  10.         if preLeft > preRight{
  11.             return nil
  12.         }
  13.         //根节点值
  14.         rootVal := preorder[preLeft]
  15.         //创建根节点
  16.         node := &TreeNode{Val:rootVal}
  17.         //判断是否有左子树,需要有这一步，不然长度会越界。
  18.         if preRight == preLeft{
  19.             return node
  20.         }
  21.         //找寻左子树根节点与根节点值
  22.         leftRoot := preLeft+1
  23.         leftRootVal := preorder[leftRoot]
  24.         //寻找左子树根节点在后序遍历中的位置
  25.         postNum := posMap[leftRootVal]
  26.         //计算左子树的长度
  27.         leftNum := postNum-postLeft+1
  28.         //创建左子树节点
  29.         node.Left = build(leftRoot,leftRoot+leftNum-1,postLeft,postNum)
  30.         //创建右子树节点
  31.         node.Right = build(leftRoot+leftNum,preRight,postNum+1,postRight-1)
  32.         return node
  33.     }
  34.     return build(0,len(preorder)-1,0,len(postorder)-1)
  35. }

1008. 前序遍历构造二叉搜索树 中等

给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：
输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2:
输入: preorder = [1,3]
输出: [1,null,3]

提示：
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值 互不相同

题解概要：

1.二叉搜索树中，第一个元素是根节点，第一次出现比根节点大的数时是右子树的根节点。

代码：

  1. func bstFromPreorder(preorder []int) *TreeNode {
  3.     var build func(int,int)*TreeNode
  4.     build = func(left int,right int)*TreeNode{
  5.         if left > right {
  6.             return nil 
  7.         }
  8.         //根节点值
  9.         rootVal := preorder[left]
  10.         //创建节点
  11.         node := &TreeNode{Val:rootVal}
  12.         if right == left{
  13.             return node
  14.         }
  15.         //求右子树根节点的位置,如果没有找到，则说明右子树为nil 
  16.         rightRootIndex := findRightNode(preorder,left,right,rootVal)
  17.         if rightRootIndex == -1{
  18.             node.Left = build(left+1,right)
  19.         }else{
  20.             //创建左子树
  21.             node.Left = build(left+1,rightRootIndex-1)
  22.             //创建右子树
  23.             node.Right = build(rightRootIndex,right)   
  24.         }
  25.         return node
  26.     }
  27.     return build(0,len(preorder)-1)
  28. }
  30. //返回的是索引
  31. func findRightNode(preorder []int,left int,right int,target int)int{
  32.     for i:= left;i<=right;i++{
  33.         if preorder[i] > target{
  34.             return i
  35.         }
  36.     }
  37.     return -1
  38. }

297. 二叉树的序列化与反序列化 困难

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

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：
输入：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]

提示：
树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000

题解概要：

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/shou-hui-tu-jie-gei-chu-dfshe-bfsliang-chong-jie-f/

代码：

  1.  import "fmt"
  2.  import "strings"
  3. type Codec struct {
  5. }
  7. func Constructor() Codec {
  8.     return Codec{}
  9. }
  11. // Serializes a tree to a single string.
  12. func (this *Codec) serialize(root *TreeNode) string {
  14.     if root == nil{
  15.         return "#"
  16.     }
  18.     return strconv.Itoa(root.Val) + "," + this.serialize(root.Left)  + "," +  this.serialize(root.Right)
  20. }
  22. // Deserializes your encoded data to tree.
  24. func (this *Codec) deserialize(data string) *TreeNode {
  26.     treeList := strings.Split(data,",")
  28.     var build func()*TreeNode 
  30.     build = func()*TreeNode{
  31.         rootStr := treeList[0]
  32.         treeList = treeList[1:]
  33.         if rootStr == "#"{
  34.             return nil
  35.         }
  36.         rootVal,_ := strconv.Atoi(rootStr)
  37.         node := &TreeNode{Val:rootVal}
  38.         node.Left = build()
  39.         node.Right = build()
  40.         return node
  41.     }
  42.     return build()
  43. }

331. 验证二叉树的前序序列化 中等

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

  1.  _9_<br />    /   \<br />   3     2<br />  / \   / \<br /> 4   1  #  6<br />/ \ / \   / \<br /># # # #   # #<br />例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,,3” 。

示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true

示例 2:
输入: “1,#”
输出: false

示例 3:
输入: “9,#,#,1”
输出: false

题解概要：

https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/

代码：

  1. func isValidSerialization(preorder string) bool {
  3.     preList := strings.Split(preorder,",")
  5.     stack := []string{}
  7.     for _,v := range preList{
  9.         stack = append(stack,v)
  10.         for len(stack) > 2 && stack[len(stack)-1] == "#" && stack[len(stack)-2] == "#" && stack[len(stack)-3] != "#"{
  11.             stack[len(stack)-3] = "#"
  12.             stack = stack[:len(stack)-2]
  13.         }
  15.     }
  16.     return len(stack) == 1 && stack[0] == "#"
  17. }

9. 字典树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：

树、广度优先、深度优先 - 图25

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

字典树的相关介绍：https://blog.csdn.net/lisonglisonglisong/article/details/45584721

208. 实现 Trie (前缀树) 中等

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

代码：

  1. type Trie struct {
  2.     children [26]*Trie
  3.     IsEnd bool  //当前字符是否为结尾
  4. }
  7. func Constructor() Trie {
  8.     return Trie{}
  9. }
  12. func (this *Trie) Insert(word string)  {
  13.     node := this
  14.     for _,ch := range word{
  15.         ch -= 'a'
  16.         //判断当前字符是否存在字典树中，不存在则新建
  17.         if node.children[ch] == nil{
  18.             node.children[ch] = &Trie{}
  19.         }
  20.         node = node.children[ch]
  21.     }
  22.     node.IsEnd = true
  23. }
  25. //查找是否有以当前前缀结尾的字符
  26. func (this *Trie) SearchPrefix(word string)*Trie{
  27.     node := this
  28.     for _,ch := range word{
  29.         ch -= 'a'
  30.         if node.children[ch] == nil{
  31.             return nil
  32.         }
  33.         node = node.children[ch]
  34.     }
  35.     return node
  36. }
  39. func (this *Trie) Search(word string) bool {
  40.     node := this.SearchPrefix(word)
  41.     return node != nil && node.IsEnd
  42. }
  45. func (this *Trie) StartsWith(prefix string) bool {
  46.     return this.SearchPrefix(prefix) != nil
  47. }

386. 字典序排数 中等

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：
输入：n = 2
输出：[1,2]

提示：

  • 1 <= n <= 5 * 104

代码：

  1. func lexicalOrder(n int) []int {
  2.     ans := []int{}
  3.     num := 1
  4.     for len(ans) < n{
  5.         //进入下一层
  6.         for num <= n{
  7.             ans = append(ans,num)
  8.             num *= 10
  9.         }
  10.         //返回上一层
  11.         for num % 10 == 9 || num > n{
  12.             num /= 10
  13.         }
  14.         num ++
  15.     }
  16.     return ans
  17. }

440. 字典序的第K小数字 困难

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:
输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:
输入: n = 1, k = 1
输出: 1

提示:
1 <= k <= n <= 109

题解概要：

1.这道题最简单的思路就是按照386题的解法，不断打印找到目标数，但效率很慢，当n和k很大时，会超时。
2.这道题不需要找到每一个数。只需要求出k具体是在哪个前缀树上即可。比如，当n=13时，以1为前缀时，一共有5个数字。分别为：1，10，11，12，13。如果此时k小于5，则说明k一定在1为前缀的树上。那么我们进入下一层，让prefix等于10，再判断k是否再前缀为10的树上，依次类推。
https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/shi-cha-shu-qiu-jie-dian-shu-liang-bu-du-d9yw/

代码：

  1. func findKthNumber(n int, k int) int {
  2.     prefix := 1
  3.     count := 1
  4.     for count < k{
  5.         cnt := getCount(prefix,n)
  6.         if count+cnt <= k{
  7.             //说明不在当前的前缀上
  8.             prefix ++
  9.             count += cnt
  10.         }else{
  11.             //在该前缀上，进入下一层
  12.             prefix *= 10
  13.             count ++
  14.         }
  15.     }
  16.     return prefix
  17. }
  19. //找到前缀树上的数量
  20. func getCount(prefix int,n int)int{
  21.     next := prefix + 1
  22.     count := 0
  23.     for prefix <= n{
  24.         count += min(n+1,next) - prefix
  25.         prefix *= 10
  26.         next *= 10
  27.     }
  28.     return count
  29. }
  31. func min(a,b int)int{
  32.     if a < b{
  33.         return a
  34.     }
  35.     return b
  36. }