[TOC]
二叉树的遍历方式
144. 二叉树的前序遍历【简单】
// https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
// 前序遍历是根左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。
//为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
func preorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
stack := []*TreeNode{root}
for len(stack) != 0 {
node := stack[len(stack)-1]
fmt.Println(node)
if node == nil {
stack = stack[:len(stack)-1]
continue
}
ans = append(ans, node.Val)
stack = stack[:len(stack)-1] // 栈顶元素出来
stack = append(stack, node.Right) // 先压栈右节点，再压左节点
stack = append(stack, node.Left)
}
return ans
}
145. 二叉树的后序遍历【简单】
94. 二叉树的中序遍历【简单】
102. 二叉树的层序遍历【中等】
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) != 0 {
var curLevel []int
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
curLevel = append(curLevel, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}
res = append(res, curLevel)
}
return res
}
107. 二叉树的层序遍历 II（中等）
func revers(input [][]int) [][]int {
row := len(input)
var res [][]int
for i := row - 1; i >= 0; i-- {
res = append(res, input[i])
}
return res
}
二叉树的属性
//**************** 解法一（递归走起）********************************
//1.判断当前节点的值是否相当
//2.递归判断左子树、右子树是否相等
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q != nil {
return false
}
if p != nil && q == nil {
return false
}
if p == nil && q == nil {
return true
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
101. 对称二叉树【简单】
104. 二叉树的最大深度【简单】
//**************** 解法一（递归走起）********************************
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
left := maxDepth(root.Left) // 左子树的最大深度
right := maxDepth(root.Right) // 右子树的最大深度
return int(math.Max(float64(left), float64(right)) + 1) // 深度加上根节点
}
//**************** 解法二（迭代法走起）********************************
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root} // 辅助队列,根节点入队
depth := 0 // 初始化深度为0
for len(queue) > 0 { // 当队列不为空时，循环以下操作
size := len(queue) //当前队列中元素个数size作为限定:当前层级中节点数量
for i := 0; i < size; i++ { // 遍历当前层级中的节点
s := queue[0] // 获取队首元素
if s.Left != nil { // 如果左子树不为空，左子树入队
queue = append(queue, s.Left)
}
if s.Right != nil { // 如果右子树不为空，右子树入队
queue = append(queue, s.Right)
}
queue = queue[1:] // 队首元素出队
}
depth++ // for循环结束后这一层级节点已经访问结束，深度加+1
}
return depth
}
111. 二叉树的最小深度【简单】
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
var queue []*TreeNode // 查找队列
queue = append(queue, root) // 将起点加入队列
depth := 1 // root 本身就是一层，depth初始化为1
for len(queue) != 0 {
size := len(queue)
// 将当前队列中的所有结点向四周扩散
for i := 0; i < size; i++ {
cur := queue[0]
// 判断是否到终点
if cur.Left == nil && cur.Right == nil {
return depth
}
// 将 cur的相邻节点加入队列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
// 去掉当前节点
queue = queue[1:]
}
// 这里增加步数
depth++
}
return depth
}
// ============== 解法二： DFS ================
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left != nil && root.Right == nil {
return 1 + minDepth(root.Left)
}
if root.Right != nil && root.Left == nil {
return 1 + minDepth(root.Right)
}
return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}
222. 完全二叉树的节点个数（中等）
110. 平衡二叉树（中等）
257. 二叉树的所有路径（简单）
404. 左叶子之和【简单】
513. 找树左下角的值【中等】
112. 路径总和【简单】
二叉树的修改和构造
226. 翻转二叉树【简单】
106. 从中序与后序遍历序列构造二叉树 （中等）
654. 最大二叉树（中等）
617. 合并二叉树【简单】
求二叉搜索树的属性
98. 验证二叉搜索树
501. 二叉搜索树中的众数（简单）
530. 二叉搜索树的最小绝对差
538. 把二叉搜索树转换为累加树（中等）
700. 二叉搜索树中的搜索（简单）
二叉树公共祖先问题
235. 二叉搜索树的最近公共祖先（简单）
236. 二叉树的最近公共祖先（中等）
// ================== 解法一： DFS 解法 ======================
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
// 如果p,q为根节点，则公共祖先为根节点
if root.Val == p.Val || root.Val == q.Val {
return root
}
// 如果p,q在左子树，则公共祖先在左子树查找
if find(root.Left, p) && find(root.Left, q) {
return lowestCommonAncestor(root.Left, p, q)
}
// 如果p,q在右子树，则公共祖先在右子树查找
if find(root.Right, p) && find(root.Right, q) {
return lowestCommonAncestor(root.Right, p, q)
}
// 如果p,q分属两侧，则公共祖先为根节点
return root
}
func find(root, c *TreeNode) bool {
if root == nil {
return false
}
if root.Val == c.Val {
return true
}
return find(root.Left, c) || find(root.Right, c)
}
// ====== 解法二 利用hash表和存储走过的路 ==============
/*思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点
，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
算法：从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA节点。*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
parent := map[int]*TreeNode{}
visited := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(r *TreeNode) {
if r == nil {
return
}
if r.Left != nil {
parent[r.Left.Val] = r
dfs(r.Left)
}
if r.Right != nil {
parent[r.Right.Val] = r
dfs(r.Right)
}
}
dfs(root)
for p != nil {
visited[p.Val] = true
p = parent[p.Val]
}
for q != nil {
if visited[q.Val] {
return q
}
q = parent[q.Val] // 从q往上找父节点
}
return nil
}
1257. 最小公共区域(会员/中等/LCA)
给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。
很自然地，如果区域 X 包含区域 Y ，那么区域 X 比区域 Y 大。
给定两个区域 region1 和 region2 ，找到同时包含这两个区域的 最小 区域。
如果区域列表中 r1 包含 r2 和 r3 ，那么数据保证 r2 不会包含 r3 。
数据同样保证最小公共区域一定存在。
/*
输入：
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
输出："North America"
*/
/
思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 region1 结点开始不断往上跳，并记录已经访问过的节点
，再从 region2 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
*/
func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
parent := make(map[string]string)
visited := make(map[string]bool)
row, _ := len(regions), len(regions[0])
for i := 0; i < row; i++ {
for j := 0; j < len(regions[i]); j++ {
if j == 0 { // 很重要，这里必须要把根节点去了
continue
}
parent[regions[i][j]] = regions[i][0]
}
}
// fmt.Println(parent)
for region1 != "" { // 这里为啥是!=" 呢，因为最上的根节点earth没有父节点，他的父节点就是”“
visited[region1] = true
region1 = parent[region1]
}
for region2 != "" {
if visited[region2] {
return region2
}
region2 = parent[region2] // 从q往上找父节点
}
return ""
}
