08-二叉树递归解题思路.md

[TOC]
# 1 二叉树的递归解法

1、 可以解决面试中的绝大部分二叉树(95%以上)的问题，尤其是树形dp问题

2、 其本质是利用递归遍历二叉树的便利性，每个节点在递归的过程中可以回到该节点3次


具体步骤为：
1. 假设以X节点为头，假设可以向X左树和右树要任何信息
2. 在上一步的假设下，讨论以X为头结点的树，得到答案的可能性（最重要），常见分类是与X无关的答案，与X有关的答案
3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4. 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
5. 递归函数都返回S，每颗子树都这么要求
6. 写代码，在代码中考虑如何把左树信息和右树信息整合出整棵树的信息

## 1.1 二叉树的递归解法实操

### 1.1.1 例一：判断二叉树平衡与否

给定一棵二叉树的头结点head，返回这颗二叉树是不是平衡二叉树

> 平衡树概念：在一棵二叉树中，每一个子树，左树的高度和右树的高度差不超过1

> 那么如果以X为头的这颗树，要做到平衡，那么X的左树要是平衡的，右树也是平衡的，且X的左树高度和右树高度差不超过1

> 所以该题，我们X需要向左右子树要的信息为，1.高度 2. 是否平衡

```Go
package main

import "math"

type Node struct {
	Val int
	Left *Node
	Right *Node
}

// BalanceInfo 表示递归过程中需要收集每个节点的信息
type BalanceInfo struct {
	// 当前节点为头的树是不是平衡的
	IsBalanced bool
	// 当前节点为头的树的高度是多少
	Height int
}

// IsBalanced 给定二叉树头节点，判断该二叉树是不是平衡二叉树
func (head *Node) IsBalanced() bool {
	return Process(head).IsBalanced
}

func Process(node *Node) *BalanceInfo {
	if node == nil {
		return &BalanceInfo{
			IsBalanced: true,
			Height:     0,
		}
	}
	// 左子树信息
	leftInfo := Process(node.Left)
	// 右子树信息
	rightInfo := Process(node.Right)
	// 高度等于左右最大高度，加上当前头结点的高度1
	curHeight := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height))) + 1
	curIsBalanced := true
	// 左树不平衡或者右树不平衡，或者左右两子树高度差超过1
	// 那么当前节点为头的树，不平衡
	if !leftInfo.IsBalanced || !rightInfo.IsBalanced || math.Abs(float64(leftInfo.Height) -float64(rightInfo.Height)) > 1 {
		curIsBalanced = false
	}
	// 加工出当前节点的信息返回
	return &BalanceInfo{
		IsBalanced: curIsBalanced,
		Height:     curHeight,
	}
}
```

### 1.1.2 例二：返回二叉树任意两个节点最大值

给定一棵二叉树的头结点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离

> 1、有可能最大距离和当前节点X无关，即最大距离是X左树的最大距离，或者右树的最大距离

> 2、最大距离跟X有关，即最大距离通过X。左树离X最远的点，到X右树上离X最远的点。即X左树的高度加上X自身高度1，加上X右树上的高度

> 结论：那么根据递归套路，我们每次递归，需要返回X左树的最大距离和高度，同理返回X右树的最大距离和高度。Info包含最大距离和高度

```Go
package main

import "math"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

type DistanceInfo struct {
	// 当前节点为树根的情况下，该树的最大距离
	MaxDistance int
	// 当前节点为树根的情况下，该树的高度
	Height int
}

// GetMaxDistance 给定二叉树头节点，求该二叉树的最大距离
func (head *Node) GetMaxDistance() int {
	return Process(head).MaxDistance
}

func Process(node *Node) *DistanceInfo {
	// base case
	if node == nil {
		return &DistanceInfo{
			MaxDistance: 0,
			Height:      0,
		}
	}

	// 左树信息
	leftInfo := Process(node.Left)
	// 右树信息
	rightInfo := Process(node.Right)
	// 用左右树的信息，加工当前节点自身的info
	// 自身的高度是，左右较大的高度加上自身节点高度1
	curHeight := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height)))
	// 自身最大距离，(左右树最大距离)和(左右树高度相加再加1)，求最大值
	curMaxDistance := int(math.Max(
		math.Max(float64(leftInfo.MaxDistance), float64(rightInfo.MaxDistance)),
		float64(leftInfo.Height+rightInfo.Height+1)))
	// 自身的info返回
	return &DistanceInfo{
		MaxDistance: curMaxDistance,
		Height:      curHeight,
	}
}

```

### 1.1.3 例三：返回二叉树中的最大二叉搜索树Size

给定一颗二叉树的头结点head，返回这颗二叉树中最大的二叉搜索树的Size

> 搜索二叉树概念：整颗树上没有重复值，左树的值都比我小，右树的值都比我大。每颗子树都如此。

> 1、与当前节点X无关，即最终找到的搜索二叉树，不以X为头

> 2、与X有关，那么X的左树整体是搜索二叉树，右树同理，且左树的最大值小于X,右树的最小值大于X

```Go
package main

import "math"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// Info 任何子树递归过程中,都返回4个信息
type Info struct {
	// 以当前节点为头节点的树，整体是否是二叉搜索树
	IsAllBST bool
	// 最大的满足二叉搜索树树条件的size
	MaxSubBSTSize int
	// 整棵树的最小值
	Min int
	// 整棵树的最大值
	Max int
}

// MaxSubBSTSize 给定二叉树头节点，返回该二叉树的最大二叉搜索子树的大小
func (head *Node) MaxSubBSTSize() int {
	if head == nil {
		return 0
	}
	return process(head).MaxSubBSTSize
}

func process(node *Node) *Info {
	if node == nil {
		return nil
	}

	// 左子树返回的Info信息
	leftInfo := process(node.Left)
	// 右子树返回的Info信息
	rightInfo := process(node.Right)

	// 加工我自身的info
	min,max := node.Val, node.Val
	// 左树不为空，加工min和max
	if leftInfo != nil {
		min = int(math.Min(float64(min), float64(leftInfo.Min)))
		max = int(math.Max(float64(max), float64(leftInfo.Max)))
	}

	// 右树不为空，加工min和max
	if rightInfo != nil {
		min = int(math.Min(float64(min), float64(rightInfo.Min)))
		max = int(math.Max(float64(max), float64(rightInfo.Max)))
	}

	// case1: 与node无关的情况。当前二叉树存在的最大搜索二叉树的最大大小，是左右树存在的最大二叉搜索树的较大的
	maxSubBSTSize := 0
	if leftInfo != nil {
		maxSubBSTSize = leftInfo.MaxSubBSTSize
	}
	if rightInfo != nil {
		maxSubBSTSize = int(math.Max(float64(maxSubBSTSize), float64(rightInfo.MaxSubBSTSize)))
	}
	// 如果当前节点为头的二叉树不是二叉搜索树，则当前Info信息中isAllBST为false
	isAllBST := false
	
	// case2：与node有关的情况
	// 左树整个是二叉搜索树么
	leftIsAllBST := false
	// 右树整个是二叉搜索树么
	rightIsAllBST := false
	// 左树最大值小于node的值是否
	leftMaxVLessNodeV := false
	// 右树的最小值，大于node的值是否
	rightMinMoreNodeV := false
	if leftInfo == nil {
		leftIsAllBST = true
		leftMaxVLessNodeV = true
	} else {
		leftIsAllBST = leftInfo.IsAllBST
		leftMaxVLessNodeV = leftInfo.Max < node.Val
	}

	if rightInfo == nil {
		rightIsAllBST = true
		rightMinMoreNodeV = true
	} else {
		rightIsAllBST = rightInfo.IsAllBST
		rightMinMoreNodeV = rightInfo.Min > node.Val
	}
	
	// 如果左树是二叉搜索树，右树也是二叉搜索树，当前节点为树根的左树最大值都比当前值小，当前节点为树根的右树最小值都比当前值大
	// 证明以当前节点node为树根的树，也是一个二叉搜索树。满足case2
	if leftIsAllBST && rightIsAllBST && leftMaxVLessNodeV && rightMinMoreNodeV {
		leftSize := 0
		rightSize := 0
		if leftInfo != nil {
			leftSize = leftInfo.MaxSubBSTSize
		}
		
		if rightInfo != nil {
			rightSize = rightInfo.MaxSubBSTSize
		}
		
		// 当前节点为树根的二叉搜索树的节点大小是左树存在的最大二叉搜索树的大小，加上右树存在的最大的二叉搜索树的大小，加上当前node节点1
		maxSubBSTSize = leftSize + rightSize + 1
		// 当前节点整个是二叉搜索树
		isAllBST = true
	}
	
	return &Info{
		IsAllBST:      isAllBST,
		MaxSubBSTSize: maxSubBSTSize,
		Min:           min,
		Max:           max,
	}

}
```

### 1.1.4 例四：判断二叉树是否是满二叉树

给定一棵二叉树的头结点head，返回这颗二叉树是不是满二叉树。

> 思路：满二叉树一定满足2^L - 1 == N，其中L是这颗二叉树的高度，N是这颗二叉树的节点个数

```Go
package main

import "math"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// Info 包含高度信息，和节点个数信息
type Info struct {
	Height int
	Nodes  int
}

func (head *Node) IsFull() bool {
	if head == nil {
		return true
	}
	all := process(head)
	// 当前二叉树的高度乘以2 是否等于当前二叉树的节点个数，从而可以判断当前二叉树是否是满二叉树
	return all.Height*2-1 == all.Nodes
}

func process(node *Node) *Info {
	if node == nil {
		return &Info{
			Height: 0,
			Nodes:  0,
		}
	}

	leftInfo := process(node.Left)
	rightInfo := process(node.Right)
	// 当前高度
	height := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height))) + 1
	// 当前节点为树根的二叉树所有节点数
	nodes := leftInfo.Nodes + rightInfo.Nodes + 1
	return &Info{
		Height: height,
		Nodes:  nodes,
	}
}
```

### 1.1.5 例五：二叉搜索树的头结点

给定一棵二叉树的头结点head，返回这颗二叉树中最大的二叉搜索子树的头节点

和1.1.3问题的返回二叉搜索子树的Size问题类似。
- 可以在原基础上改动实现
- 也可以去掉isAllBST的信息，通过判断左树最大二搜索树的head，是不是等于当前节点的左孩子，判断右树最大二搜索树的head，是不是等于当前节点的右孩子，从而判断当前节点为头的树，整个是二叉搜索树，从而构建当前节点递归过程中的Info

```Go
package main

import "math"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// Info 任何子树递归过程中,都返回4个信息
type Info struct {
	// 当前节点为头的二叉树中，最大搜索二叉树的头结点
	MaxSubBSTHead *Node
	// 以当前节点为头节点的树，整体是否是二叉搜索树
	IsAllBST bool
	// 最大的满足二叉搜索树树条件的size
	MaxSubBSTSize int
	// 整棵树的最小值
	Min int
	// 整棵树的最大值
	Max int
}

func (head *Node) MaxSubBSTHead() *Node {
	if head == nil {
		return nil
	}
	return process(head).MaxSubBSTHead
}

func process(node *Node) *Info {
	if node == nil {
		return nil
	}

	// 左子树返回的Info信息
	leftInfo := process(node.Left)
	// 右子树返回的Info信息
	rightInfo := process(node.Right)

	min, max := node.Val, node.Val
	var maxSubBSTHead *Node
	maxSubBSTSize := 0

	// 如果当前节点为头的二叉树不是二叉搜索树，则当前Info信息中isAllBST为false
	isAllBST := false

	// case1：当前节点为头的二叉树中存在的最大搜索二叉树与当前节点node无关的情况
	// 左树不为空，加工min, max, maxSubBSTHead, maxSubBSTSize
	if leftInfo != nil {
		min = int(math.Min(float64(min), float64(leftInfo.Min)))
		max = int(math.Max(float64(max), float64(leftInfo.Max)))
		maxSubBSTHead = leftInfo.MaxSubBSTHead
		maxSubBSTSize = leftInfo.MaxSubBSTSize
	}

	// 右树不为空，加工min, max, maxSubBSTHead, maxSubBSTSize
	if rightInfo != nil {
		min = int(math.Min(float64(min), float64(rightInfo.Min)))
		max = int(math.Max(float64(max), float64(rightInfo.Max)))
		if rightInfo.MaxSubBSTSize > maxSubBSTSize {
			maxSubBSTHead = rightInfo.MaxSubBSTHead
			maxSubBSTSize = rightInfo.MaxSubBSTSize
		}
	}

	// case2: 当前节点为头的二叉树中存在的最大搜索二叉树与当前节点node有关的情况
	// 左树整个是二叉搜索树么
	leftIsAllBST := false
	// 右树整个是二叉搜索树么
	rightIsAllBST := false
	// 左树最大值小于node的值是否
	leftMaxVLessNodeV := false
	// 右树的最小值，大于node的值是否
	rightMinMoreNodeV := false
	if leftInfo == nil {
		leftIsAllBST = true
		leftMaxVLessNodeV = true
	} else {
		leftIsAllBST = leftInfo.IsAllBST
		leftMaxVLessNodeV = leftInfo.Max < node.Val
	}

	if rightInfo == nil {
		rightIsAllBST = true
		rightMinMoreNodeV = true
	} else {
		rightIsAllBST = rightInfo.IsAllBST
		rightMinMoreNodeV = rightInfo.Min > node.Val
	}

	// 如果左树是二叉搜索树，右树也是二叉搜索树，当前节点为树根的左树最大值都比当前值小，当前节点为树根的右树最小值都比当前值大
	// 证明以当前节点node为树根的树，也是一个二叉搜索树。满足case2
	if leftIsAllBST && rightIsAllBST && leftMaxVLessNodeV && rightMinMoreNodeV {
		leftSize := 0
		rightSize := 0
		if leftInfo != nil {
			leftSize = leftInfo.MaxSubBSTSize
		}

		if rightInfo != nil {
			rightSize = rightInfo.MaxSubBSTSize
		}

		maxSubBSTHead = node
		maxSubBSTSize = leftSize + rightSize + 1
		// 当前节点整个是二叉搜索树
		isAllBST = true
	}

	return &Info{
		MaxSubBSTHead: maxSubBSTHead,
		IsAllBST:      isAllBST,
		MaxSubBSTSize: maxSubBSTSize,
		Min:           min,
		Max:           max,
	}

}
```

### 1.1.6 例子六：是否是完全二叉树

给定一棵二叉树的头结点head，返回这颗二叉树是不是完全二叉树

> 完全二叉树概念在堆的章节，有介绍。

> 宽度优先遍历解决思路:

1、如果用树的宽度优先遍历的话，如果某个节点有右孩子，但是没有左孩子，一定不是完全二叉树 

2、在条件1的基础上，一旦遇到第一个左右孩子不双全的节点，后续所有节点必须为叶子节点

> 二叉树递归解法思路：

1、满二叉树（无缺口），一定是完全二叉树。此时左右树需要给X的信息是，是否是满的和高度。如果左右树满，且左右树高度一样，那么是该种情况--满二叉树

2、有缺口，1缺口可能停在当前节点左树上。左树需要给当前节点是否是完全二叉树的信息，右树需要给X是否是满二叉树的信息，且左树高度比右树高度大1

3、缺口可能在左右树的分界。左树是满的，右树也是满的，左树高度比右树大1

4、左树已经满了，缺口可能在我的右树上。左树是满的，右树是完全二叉树，且左右树高度一样

> 所以我们的递归时，需要向子树要的信息为：是否是完全二叉树，是否是满二叉树，高度

```Go
package main

import "math"

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// IsCBTWithProcess 递归二叉树判断一颗二叉树是否是完全二叉树
func (head *Node) IsCBTWithProcess() bool {
	if head == nil {
		return true
	}
	return process(head).IsCBT
}

type Info struct {
	IsFull bool
	IsCBT bool
	Height int
}

func process(node *Node) *Info  {
	// 如果是空树，我们封装Info而不是返回为空
	// 方便下文不需要额外增加判空处理
	if node == nil {
		return &Info{
			IsFull: true,
			IsCBT:  true,
			Height: 0,
		}
	}

	leftInfo := process(node.Left)
	rightInfo := process(node.Right)

	// 整合当前节点的Info
	// 高度信息=左右树最大高度值+1
	height := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height)))
	// node是否是满二叉树信息=左右都是满且左右高度一样
	isFull := leftInfo.IsFull && rightInfo.IsFull && leftInfo.Height == rightInfo.Height
	isBST := false
	if isFull { // 满二叉树是完全二叉树
		isBST = true
	} else { // 以node为头整棵树，不满
		// 左右都是完全二叉树才有讨论的必要
		if leftInfo.IsCBT && rightInfo.IsCBT {
			// 第二种情况。左树是完全二叉树，右树是满二叉树，左树高度比右树高度大1
			if leftInfo.IsCBT && rightInfo.IsFull && leftInfo.Height == rightInfo.Height + 1 {
				isBST = true
			}
			// 第三种情况。左树满，右树满，且左树高度比右树高度大1
			if leftInfo.IsFull && rightInfo.IsFull && leftInfo.Height == rightInfo.Height + 1 {
				isBST = true
			}
			// 第四种情况。左树满，右树是完全二叉树，且左右树高度相同
			if leftInfo.IsFull && rightInfo.IsCBT && leftInfo.Height == rightInfo.Height {
				isBST = true
			}
		}
	}
	return &Info{
		IsFull: isFull,
		IsCBT:  isBST,
		Height: height,
	}
}

// IsCBTWithWidth 宽度优先遍历判断一颗二叉树是否是完全二叉树
func (head *Node)IsCBTWithWidth() bool {
	if head == nil {
		return true
	}

	hd := head

	var queue = make([]*Node, 0)
	// 是否遇到过左右两个孩子不双全的节点
	leaf := false
	var l *Node = nil
	var r *Node = nil
	queue = append(queue, hd)
	for len(queue) != 0 {
		hd = queue[0]
		queue = queue[1:]
		l = hd.Left
		r = hd.Right
		// 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
		if leaf && (l != nil || r != nil) || (l == nil && r == nil) {
			return false
		}
		if l != nil {
			queue = append(queue, l)
		}
		if r != nil {
			queue = append(queue, r)
		}
		if l == nil || r == nil {
			leaf = true
		}
	}
	return true
}
```

### 1.1.7 例子七：最低公共祖先

给次那个一颗二叉树的头结点head，和另外两个节点a和b。返回a和b的最低公共祖先

二叉树的最低公共祖先概念： 任意两个节点，往父亲看，最开始交汇的节点，就是最低公共祖先

> 解法一：用辅助map，Key表示节点，Value表示节点的父亲节点。我们把两个目标节点的父亲以此放到map中，依次遍历

> 解法二：使用二叉树的递归套路。

1、o1和o2都不在以X为头的树上

2、o1和o2有一个在以X为头的树上

3、o1和o2都在以X为头的树上

3.1、X为头的树，左树右树各有一个

3.2、X为头的树，左树含有o1和o2

3.3、X为头的树，右树含有o1和o2

4、X自身就是o1或者o2，即如果X是o1那么左右树收集到o2即可，如果X是o2，左右树收集到o1即可。

```Go
package main

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// LowestAncestorByMap 给定两个树节点，求这两个节点的最低公共祖先
func (head *Node) LowestAncestorByMap(o1 *Node, o2 *Node) *Node {
	if head == nil {
		return nil
	}
	// key的父节点是value
	parentMap := make(map[*Node]*Node, 0)
	parentMap[head] = nil
	// 递归填充map
	fillParentMap(head, parentMap)
	// 辅助set
	nodeSet := make(map[*Node]string, 0)
	cur := o1
	nodeSet[cur] = ""
	// nodeSet存入的是沿途所有的父节点
	for parent, ok := parentMap[cur]; ok; {
		nodeSet[parent] = ""
	}

	cur = o2
	// o2的某个父节点在parentSet中，就是我们要找的节点
	for _, ok := parentMap[cur]; !ok; {
		// 继续向上
		cur = parentMap[cur]
	}
	return cur
}

func fillParentMap(head *Node, parentMap map[*Node]*Node) {
	if head.Left != nil {
		parentMap[head.Left] = head
		fillParentMap(head.Left, parentMap)
	}
	if head.Right != nil {
		parentMap[head.Right] = head
		fillParentMap(head.Right, parentMap)
	}
}

type Info struct {
	// o1和o2的最初交汇点，如果不是在当前这颗X节点的树上，返回空
	Ans *Node
	// 在当前子树上，是否发现过o1和o2
	FindO1 bool
	FindO2 bool
}

// LowestAncestorByProcess 递归二叉树判断任意两个节点的最低公共祖先
func (head *Node) LowestAncestorByProcess(o1, o2 *Node) *Node {
	return Process(head, o1, o2).Ans
}

func Process(node, o1, o2 *Node) *Info {
	// o1和o2不为空，那么空树上的Info如下
	if node == nil {
		return &Info{
			Ans:    nil,
			FindO1: false,
			FindO2: false,
		}
	}
	leftInfo := Process(node.Left, o1, o2)
	rightInfo := Process(node.Right, o1, o2)

	// 构建node自身需要返回的Info
	// node为头的树上是否发现了o1
	findO1 := node == o1 || leftInfo.FindO1 || rightInfo.FindO1
	// node为头的树上是否发现了o2
	findO2 := node == o2 || leftInfo.FindO2 || rightInfo.FindO2
	// 	O1和O2最初的交汇点在哪？

	// 1) 在左树上已经提前交汇了,最初交汇点保留左树的
	var ans *Node = nil
	if leftInfo.Ans != nil {
		ans = leftInfo.Ans
	}
	// 2) 在右树上已经提前交汇了，最初交汇点保留右树的
	if rightInfo.Ans != nil {
		ans = rightInfo.Ans
	}
	// 3) 没有在左树或者右树上提前交汇
	if ans == nil {
		// 但是找到了o1和o2，那么交汇点就是X自身
		if findO1 && findO2 {
			ans = node
		}
	}
	return &Info{
		Ans:    ans,
		FindO1: findO1,
		FindO2: findO2,
	}
}
```

> 二叉树的递归套路，最终转化为基于X只找可能性即可。即树形DP问题