26-附：二叉树专题汇总.md

- 二叉树基础

```Go
package main

import (
	"fmt"
	"strconv"
)

// Node 二叉树的节点定义
type Node struct {
	Value int
	Left *Node
	Right *Node
}

// 1、递归先序遍历
func pre(head *Node) {
	if head == nil {
		return
	}

	fmt.Println(head.Value)
	pre(head.Left)
	pre(head.Right)
}

// 2、递归中序遍历
func mid(head *Node) {
	if head == nil {
		return
	}

	mid(head.Left)
	fmt.Println(head.Value)
	mid(head.Right)
}

// 3、递归后序遍历
func pos(head *Node) {
	if head == nil {
		return
	}

	pos(head.Left)
	pos(head.Right)
	fmt.Println(head.Value)
}

// 4、非递归先序
func notRPre(head *Node) {
	fmt.Println("pre-order: ")

	if head != nil {
		// 借助栈结构，手动压栈
		stack := make([]*Node, 0)
		stack = append(stack, head)

		for len(stack) != 0 {
			// 弹出就打印
			head = stack[len(stack) - 1]
			stack = stack[:len(stack) - 1]

			fmt.Println(head.Value)

			// 右孩子不为空，先压入右孩子。右孩子就会后弹出
			if head.Right != nil {
				stack = append(stack, head.Right)
			}

			// 左孩子不为空，压入左孩子，左孩子在右孩子之后压栈，先弹出
			if head.Left != nil {
				stack = append(stack, head.Left)
			}
		}
	}
}

// 5、非递归中序
func notRMid(head *Node) {
	fmt.Println("mid-order: ")

	if head != nil {
		stack := make([]*Node, 0)

		for len(stack) != 0 || head != nil {
			// 整条左边界依次入栈
			if head != nil {
				stack = append(stack, head)
				// head滑到自己的左孩子，左孩子有可能为空，但空的节点不会加入栈，下一个分支会判空处理
				head = head.Left
				// 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
			} else { // head为空的情况，栈顶是上次头结点的现场，head等于栈顶，回到上一个现场。打印后，head往右树上滑动
				head = stack[len(stack) - 1]
				stack = stack[:len(stack) - 1]

				fmt.Println(head.Value)
				head = head.Right
			}
		}
	}
}

// 6、非递归后序，借助两个栈，比借助一个栈容易理解
func notRPos(head *Node) {
	fmt.Println("pos-order: ")

	if head != nil {
		stack1 := make([]*Node, 0)
		stack2 := make([]*Node, 0)

		stack1 = append(stack1, head)

		for len(stack1) != 0 {
			head = stack1[len(stack1) - 1]
			stack1 = stack1[:len(stack1) - 1]

			stack2 = append(stack2, head)
			if head.Left != nil {
				stack1 = append(stack1, head.Left)
			}
			if head.Right != nil {
				stack1 = append(stack1, head.Right)
			}
		}

		for len(stack2) != 0 {
			cur := stack2[len(stack2) - 1]
			stack2 = stack2[:len(stack2) - 1]
			fmt.Println(cur.Value)
		}
	}
	fmt.Println()
}

// 7、非递归后序,仅借助一个栈，比较有技巧
func notRPos2(head *Node) {
	fmt.Println("pos-order: ")

	if head != nil {
		stack := make([]*Node, 0)
		stack = append(stack, head)
		var c *Node

		for len(stack) != 0 {
			c = stack[len(stack) - 1] // stack peek
			if c.Left != nil && head != c.Left && head != c.Right {
				stack = append(stack, c.Left)
			} else if c.Right != nil && head != c.Right {
				stack = append(stack, c.Right)
			} else {
				stack = stack[:len(stack) - 1] // pop
				fmt.Println(c.Value)
				head = c
			}
		}
	}
	fmt.Println()
}

// 8、按层遍历，即宽度优先遍历
func level(head *Node) {
	if head == nil {
		return
	}

	queue := make([]*Node, 0)
	queue = append(queue, head)

	for len(queue) != 0 {
		cur := queue[0] // queue poll
		queue = queue[1:]

		// 打印当前
		fmt.Println(cur.Value)

		// 当前节点有左孩子，加入左孩子进队列
		if cur.Left != nil {
			queue = append(queue, cur.Left)
		}
		// 当前节点有右孩子，加入右孩子进队列
		if cur.Right != nil {
			queue = append(queue, cur.Right)
		}
	}
}

// 9、二叉树的先序序列化
func preSerial(head *Node) []string {
	ansQueue := make([]string, 0)

	pres(head, ansQueue)
	return ansQueue
}

func pres(head *Node, ans []string) {
	if head == nil {
		ans = append(ans, "")
	} else {
		ans = append(ans, fmt.Sprintf("%d", head.Value))
		pres(head.Left, ans)
		pres(head.Right, ans)
	}
}

// 10、根据先序序列化的结果，反序列化成一颗树
func buildByPreQueue(prelist []string) *Node {
	if len(prelist) == 0 {
		return nil
	}

	return preb(prelist)
}

func preb(prelist []string) *Node {
	value := prelist[0]
	prelist = prelist[1:]

	// 如果头节点是空的话，返回空
	if value == "" {
		return nil
	}

	// 否则根据第一个值构建先序的头结点
	v, _ := strconv.Atoi(value)
	head := &Node{
		Value: v,
		Left:  nil,
		Right: nil,
	}
	// 递归建立左树
	head.Left = preb(prelist)
	// 递归建立右树
	head.Right = preb(prelist)
	return head
}
```

- 二叉树应用

```Go
package main

import "math"

// Node 二叉树的节点定义
type Node struct {
	Value int
	Left *Node
	Right *Node
}


// IsBalanced 1、判断二叉树是否是平衡的
func IsBalanced(head *Node) bool {
	return isBalancedProcess(head).isBalanced
}

// 递归过程信息
type isBalancedInfo struct {
	isBalanced bool
	height int
}

// 递归调用，head传入整体需要返回一个信息
// 解决当前节点的Info信息怎么得来
func isBalancedProcess(head *Node) *isBalancedInfo {
	if head == nil {
		return &isBalancedInfo{
			isBalanced: true,
			height:     0,
		}
	}

	leftInfo := isBalancedProcess(head.Left)
	rightInfo := isBalancedProcess(head.Right)

	// 当前节点的高度，等于左右树最大的高度，加上当前节点高度1
	cHeight := int(math.Max(float64(leftInfo.height), float64(rightInfo.height))) + 1
	isBalanced := true

	if !leftInfo.isBalanced || !rightInfo.isBalanced || int(math.Abs(float64(leftInfo.height - rightInfo.height))) > 1 {
		isBalanced = false
	}

	return &isBalancedInfo{
		isBalanced: isBalanced,
		height:     cHeight,
	}
}

// MaxDistance 2、二叉树中，获取任意两个节点的最大距离
func MaxDistance(head *Node) int {
	return maxDistanceProcess(head).maxDistance
}

type maxDistanceInfo struct {
	maxDistance int
	height int
}

func maxDistanceProcess(head *Node) *maxDistanceInfo {
	if head == nil {
		return &maxDistanceInfo{
			maxDistance: 0,
			height:      0,
		}
	}

	leftInfo := maxDistanceProcess(head.Left)
	rightInfo := maxDistanceProcess(head.Right)

	// 当前节点为头的情况下，高度等于左右树较大的高度，加上1
	height := int(math.Max(float64(leftInfo.height), float64(rightInfo.height))) + 1

	// 当前节点为头的情况下，最大距离等于，左右树距离较大的那个距离(与当前节点无关的情况)
	// 和左右树高度相加再加上当前节点距离1的距离(与当前节点有关的情况)取这两种情况较大的那个
	maxDistance := int(math.Max(math.Max(float64(leftInfo.maxDistance), float64(rightInfo.maxDistance)),
		float64(leftInfo.height + rightInfo.height + 1)))

	return &maxDistanceInfo{
		maxDistance: maxDistance,
		height:      height,
	}
}

// IsFull 3、判断一颗树是否是满二叉树
func IsFull(head *Node) bool {
	if head == nil {
		return true
	}

	all := isFullProcess(head)

	return (1 << all.height) - 1 == all.nodes
}

// 判断一棵树是否是满二叉树，每个节点需要返回的信息
type isFullInfo struct {
	height int
	nodes int
}

func isFullProcess(head *Node) *isFullInfo {
	if head == nil {  // base 空节点的高度为0，节点数量也0
		return &isFullInfo{
			height: 0,
			nodes:  0,
		}
	}

	leftInfo := isFullProcess(head.Left)
	rightInfo := isFullProcess(head.Right)

	// 当前节点为头的树，高度
	height := int(math.Max(float64(leftInfo.height), float64(rightInfo.height)) + 1)
	// 当前节点为头的树，节点数量
	nodes := leftInfo.nodes + rightInfo.nodes + 1

	return &isFullInfo{
		height: height,
		nodes:  nodes,
	}
}

// GetMaxLength 4、找到二叉树中节点和等于sum的最长路径
func GetMaxLength(head *Node, sum int) int {
	sumMap := make(map[int]int, 0)
	sumMap[0] = 0

	return preOrder(head, sum, 0, 1, 0, sumMap)
}

func preOrder(head *Node, sum int, preSum int, level int, maxLen int, sumMap map[int]int) int {
	if head == nil {
		return maxLen
	}

	curSum := preSum + head.Value
	if _, ok := sumMap[curSum]; !ok {
		sumMap[curSum] = level
	}

	if v, ok := sumMap[curSum - sum]; ok {
		maxLen = int(math.Max(float64(level - v), float64(maxLen)))
	}

	maxLen = preOrder(head.Left, sum, curSum, level + 1, maxLen, sumMap)
	maxLen = preOrder(head.Right, sum, curSum, level + 1, maxLen, sumMap)

	if level == sumMap[curSum] {
		delete(sumMap, curSum)
	}

	return maxLen
}

// LowestCommonAncestor 5、二叉树，给定头结点节点，及树上的两个人节点，求这两个节点的最近公共祖先
func LowestCommonAncestor(root *Node, p *Node, q *Node) *Node {
	// 如果树为空，直接返回null；
	// 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
	if root == nil || p == root || q == root {
		return root
	}

	// 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
	left := LowestCommonAncestor(root.Left, p, q)
	// 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
	right := LowestCommonAncestor(root.Right, p, q)

	// left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
	if left != nil && right != nil {
		return root
	}

	// 如果在左子树中p和q都找不到，则p和q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
	// 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，
	// 如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
	if left == nil {
		return right
	} else {
		return left
	}
}

// IsSymmetric 6、给定一个二叉树头节点，判断这颗树是否是镜面堆成的。即是否是是镜像二叉树
func IsSymmetric(root *Node) bool {
	// 自身，和自身的镜像树去递归比较
	return isMirror(root, root)
}

// 一棵树是原始树  head1
// 另一棵是翻面树  head2
func isMirror(head1, head2 *Node) bool {
	// base case 当前镜像的节点都为空，也算合法的镜像
	if head1 == nil && head2 == nil {
		return true
	}

	// 互为镜像的两个点不为空
	if head1 != nil && head2 != nil {
		// 当前两个镜像点要是相等的，
		// A树的左树和B树的右树互为镜像且满足，且A树的右树和B树的左树互为镜像，且满足。
		// 那么当前的镜像点下面的都是满足的
		return head1.Value == head2.Value && isMirror(head1.Left, head2.Right) && isMirror(head1.Right, head2.Left)
	}
	// 一个为空，一个不为空 肯定不构成镜像  false
	return false
}
```