5. 二叉树
5.0 二叉树递归套路
1）假设以X节点为头，假设可以向X左树和X右树要任何信息
2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
5）递归函数都返回S，每一棵子树都这么要求
6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
5.1 前中后序递归遍历
5.2 前中后序非递归遍历
1. 题目
非递归遍历二叉树，各种方式。
2. 思路
前序遍历 ： 是头左右，用栈，由于遍历顺序是根左右，所以入栈顺序是根右左。
后序遍历：是左右头，可以先用栈按头右左的顺序遍历（改前序），而后把这些用另一个栈保存起来，相当于逆序输出，也就变成了左右头。
中序遍历：是左头右，先让左孩子的入栈，直到左孩子为空，弹出并且打印，而后让右孩子入栈。
3. 代码
先根遍历：
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList();
}
List<Integer> ans = new ArrayList<>();
// 前序遍历用栈
// 跟左右 -- 入栈：根右左
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode cur = stack.pop();
ans.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
return ans;
}
后序遍历：
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList();
}
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
// 想要左右根的顺序 - 用栈，逆序的根右左就是左右根
// 第一次遍历：需要根右左 - 入栈需要根左右
while(!s1.empty()){
TreeNode cur = s1.pop();
s2.push(cur);
if(cur.left != null){
s1.push(cur.left);
}
if(cur.right != null){
s1.push(cur.right);
}
}
// 第二次遍历：根右左 -逆序，左右根
while(!s2.empty()){
ans.add(s2.pop().val);
}
return ans;
}
中序遍历：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
TreeNode cur = root;
if(root == null){
return ans;
}
while(!s.empty() ||cur != null){
// 左侧还有孩子
if(cur != null){
s.push(cur);
cur = cur.left;
}else{
//右侧
cur = s.pop();
ans.add(cur.val);
cur = cur.right;
}
}
return ans;
}
5.3 层次遍历
1. 题目
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/ \
3 2
/ \ \
5 3 9
示例2：
输入: root = [1,2,3]
输出: [1,3]
解释:
1
/ \
2 3
示例3：
输入: root = [1]
输出: [1]
示例4：
输入: root = [1,null,2]
输出: [1,2]
解释:
1
\
2
示例5：
输入: root = []
输出: []
2. 思路
首先是层次遍历，利用队列，当前节点出队，把子节点都加进来，直到队列为空即可。
而求每一层的最大值需要我们确定每一层。考虑到每一层的规律是刚开始新的一层之前，队列里都是同一层的，所以再加一个新的循环来输出同一层的所有节点并且找到最大值，记录下去即可。
public List<Integer> largestValues(TreeNode root) {
// 层次遍历
if(root == null){
return new LinkedList<>();
}
Queue<TreeNode> queue = new ArrayDeque<>();
List<Integer> ans = new LinkedList<>();
queue.add(root);
// 需要队列保存
// 队列不空就继续
while(!queue.isEmpty()){
int len = queue.size();
int max = Integer.MIN_VALUE;
// 一层装满就可以下一层
while(len > 0){
TreeNode cur = queue.remove();
if(cur.val > max){
max = cur.val;
}
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
len--;
}
ans.add(max);
}
return ans;
}
5.4 求祖先节点
1. 题目
给定前序遍历后续遍历求某个节点的一系列祖先节点。
2. 思路
以这个节点为界限，保留先序遍历的左侧，和后续遍历的右侧，二者的交集就是此节点的父节点。
因为某节点先根遍历的左侧是同辈靠左的节点和父节点以及他们靠左的节点。而后根遍历的右侧就是同辈靠右的节点和和父节点以及他们靠右的节点。所以二者的交集就是祖先节点。并且从上往下的顺序可以看先序的顺序，从下往上可以看后序的顺序。
3. 代码
5.5 序列化/反序列化 - 先序
1. 题目
https://leetcode.cn/problems/h54YBf
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
2. 思路
序列化：先序遍历的顺序，但是null也入栈，并且打印的时候加上null作为叶节点。
反序列化：把String转为队列，而后按照先序消费（递归）节点。
3. 代码
序列化：
public String serialize(TreeNode root) {
if(root == null){
return "null";
}
// 前序序列化 -前序遍历二叉树，弹出改成序列化
// 根右左
Stack<TreeNode> stack = new Stack<>();
StringBuffer sb = new StringBuffer();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != root){
sb.append(",");
}
if(cur != null){
sb.append(String.valueOf(cur.val));
stack.push(cur.right);
stack.push(cur.left);
}else{
sb.append("null");
}
}
System.out.println(sb.toString());
return sb.toString();
}
反序列化：
public TreeNode deserialize(String data) {
String[] tree = data.split(",");
Queue<String> dataList = new LinkedList<String>(Arrays.asList(tree));
return process(dataList);
}
public TreeNode process(Queue<String> list){
if("null".equals(list.peek())){
list.remove();
return null;
}
String str = list.remove();
// System.out.println(str);
TreeNode head = new TreeNode(Integer.valueOf(str));
head.left = process(list);
head.right = process(list);
return head;
}
5.6 序列化/反序列化 - 后序
1. 题目
https://leetcode.cn/problems/h54YBf
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
2. 思路
序列化：正常的后序遍历，把正常的输出改成加入到stringbuffer中即可。
反序列化：不能直接从前往后遍历，因为从前往后会出现第一个就是null的情况让程序直接退出。所以考虑从后往前遍历。从后往前顺序就是从根左右变成了根右左，然后按照这个顺序新建节点即可。
3. 代码
序列化：
public String serialize(TreeNode root) {
StringBuffer sb = new StringBuffer();
if(root == null){
return "null";
}
// 后序遍历
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
while(!s1.isEmpty()){
TreeNode cur = s1.pop();
s2.push(cur);
if(cur != null){
s1.push(cur.left);
s1.push(cur.right);
}
}
TreeNode firstNode = s2.pop();
if(firstNode == null){
sb.append("null");
}else{
sb.append(String.valueOf(firstNode.val));
}
while(!s2.isEmpty()){
sb.append(",");
TreeNode curr = s2.pop();
if(curr == null){
sb.append("null");
}else{
sb.append(String.valueOf(curr.val));
}
}
// System.out.println(sb.toString());
return sb.toString();
}
反序列化：
public TreeNode deserialize(String data) {
String[] strs = data.split(",");
// 因为构造节点需要从根开始，有了根才能有左右节点。
// 所以需要逆向消费:左右根 -> 根右左
Stack<String> stack = new Stack<>();
for(int i = 0; i < strs.length; i++){
stack.push(strs[i]);
}
return press(stack);
}
public TreeNode press(Stack<String> stack){
String val = stack.pop();
if("null".equals(val)){
return null;
}
TreeNode head = new TreeNode(Integer.valueOf(val));
head.right = press(stack);
head.left = press(stack);
return head;
}
5.7 序列化/反序列化 - 层次
1. 题目
https://leetcode.cn/problems/h54YBf
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
2. 思路
序列化：正常层次遍历即可，打印改成加入stringbuffer。
不需要分层
反序列化：类似于正常的层次遍历，自己建立一个队列，将根加入，并且每次建立当前节点的左右孩子（如果为空就停止建立，并且空不需要加入新建的队列中。
3. 代码
序列化：
// 写复杂了，不需要分层
public String serialize(TreeNode root) {
if(root == null){
return "null";
}
// 层次遍历
Queue<TreeNode> que = new LinkedList<>();
StringBuffer sb = new StringBuffer();
que.add(root);
while(!que.isEmpty()){
int len = que.size();
// 每层都弹出并且记录
// 不需要考虑多少层
for(int i = 0; i < len; i++){
TreeNode cur = que.remove();
if(cur != root){
sb.append(",");
}
if(cur != null){
sb.append(String.valueOf(cur.val));
que.add(cur.left);
que.add(cur.right);
}else{
sb.append("null");
}
}
}
// System.out.println(sb.toString());
return sb.toString();
}
反序列化：
public TreeNode deserialize(String data) {
// string - > string[]
String[] strs = data.split(",");
// string[] -> queue
Queue<String> que = new LinkedList<>(Arrays.asList(strs));
Queue<TreeNode> nodeQue = new LinkedList<>();
TreeNode head = strToNode(que.remove());
if(head == null){
return null;
}
nodeQue.add(head);
while(!nodeQue.isEmpty()){
TreeNode tn = nodeQue.remove();
tn.left = strToNode(que.remove());
tn.right = strToNode(que.remove());
if(tn.left != null){
nodeQue.add(tn.left);
}
if(tn.right != null){
nodeQue.add(tn.right);
}
}
return head;
}
public TreeNode strToNode(String data){
if("null".equals(data)){
return null;
}
return new TreeNode(Integer.valueOf(data));
}
5.8 多叉树<-->二叉树
1. 题目
将一棵n叉树编码为一棵二叉树，并对二叉树进行解码，得到原始的n叉树。 n叉树是一棵有根树，其中每个节点的子树不超过n个。 类似地，二叉树是一棵有根树，其中每个节点的子树不超过2个。 编码/解码算法的工作方式不受限制。 您只需要确保一个n叉树可以被编码为一个二叉树，并且这个二叉树可以被解码为原始的n叉树结构。
2. 思路
多叉树-> 二叉树 ：根节点不变，大儿子节点变成二叉树的左树，所有弟节点依次变成兄节点的右子树也就是左为孩子，右为兄弟。
多叉树 -> 二叉树：en函数：将children串成右节点，左节点进行en
二叉树 -> 多叉树 : de函数：根节点不变，右树加入到children中，顺便左树de。
3. 代码
public TreeNode encode(Node root){
if(root == null){
return null;
}
TreeNode head = new TreeNode(root.val);
// 左子树为大孩子
head.left = en(root.children);
return head;
}
/**
* 将兄弟节点挂载到右子树上- 对错存疑，没vip
* @param children
* @return
*/
public TreeNode en(List<Node> children) {
if(children.size() == 0){
return null;
}
TreeNode head = new TreeNode(children.get(0).val);
TreeNode cur = head;
int len = children.size();
for (int i = 1; i < len; i++) {
Node curNode = children.get(i);
cur.right = new TreeNode(curNode.val);
cur.left = en(curNode.children);
cur = cur.right;
}
return head;
}
public Node decode(TreeNode root){
if(root == null){
return null;
}
Node head = new Node(root.val,de(root.left));
return head;
}
/**
* 将右孩子（兄弟）添加到children中，返回给父节点
* @param root
* @return
*/
private List<Node> de(TreeNode root) {
List<Node> children = new ArrayList<>();
while(root != null){
Node cur = new Node(root.val,de(root.left));
children.add(cur);
root = root.right;
}
return children;
}
5.9 判断完全二叉树(CBT)
- 有右孩子无左孩子一定不是
- 第一次遇到左右不全的节点，之后的节点一定是叶节点
5.10 判断平衡二叉树
1. 题目
平衡二叉树是指，每一个节点左右子树的高度相差不超过1。
2. 思路
平衡二叉树要求：
1. 左子树为平衡二叉树
1. 右子树为平衡二叉树
1. 左右子树高度相差不超过1(<=1)
基于此，建立类Info存两个信息：当前树的高度，是否为平衡二叉树。
递归proces函数，输入节点，输出Info。含义是判断以这个节点为根的树是不是平衡二叉树，并且根为多少。
3. 代码
Info
public static class Info{
public boolean isBalanced;
public int height;
public Info(boolean i， int h) {
isBalanced = i;
height = h;
}
}
process
public static Info process(Node x) {
if(x == null) {
return new Info(true，0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height，rightInfo.height) + 1;
boolean isBalanced = true;
if(!leftInfo.isBalanced) {
isBalanced = false;
}
if( !rightInfo.isBalanced) {
isBalanced = false;
}
if(Math. abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
return new Info(isBalanced，height);
}
5.11 判断搜索二叉树(BST)
1. 题目
搜索二叉树：左子树的值都比根小，右子树的值都比根大。
如果相等，多个值占同一个节点，本题不考虑
2. 思路
搜索二叉树要求：
- 左是搜索二叉树
- 右是搜索二叉树
- max（左子树）< 当前节点
- min（右子树）> 当前节点
所以Info里有三个信息：是否是搜索二叉树，min，max。
对于空：如果你不知道怎么处理空，直接返回null，在递归上游处理空。
3. 代码
Info
public static class Info {
public boolean isBST;
public int max;
public int min;
public Info(boolean i, int ma, int mi) {
isBST = i;
max = ma;
min = mi;
}
}
process
public static Info process(Node x) {
if (x == null) {
return null;
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.value;
if (leftInfo != null) {
max = Math.max(max, leftInfo.max);
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
}
int min = x.value;
if (leftInfo != null) {
min = Math.min(min, leftInfo.min);
}
if (rightInfo != null) {
min = Math.min(min, rightInfo.min);
}
boolean isBST = true;
if (leftInfo != null && !leftInfo.isBST) {
isBST = false;
}
if (rightInfo != null && !rightInfo.isBST) {
isBST = false;
}
if (leftInfo != null && leftInfo.max >= x.value) {
isBST = false;
}
if (rightInfo != null && rightInfo.min <= x.value) {
isBST = false;
}
return new Info(isBST, max, min);
}
5.12 返回二叉树的最大距离
1. 题目
找到二叉树从一个节点到另一个节点的距离，返回最大的距离。
2. 思路
最大距离的可能情况：
- 左子树到当前节点的最大距离
- 右子树到当前节点的最大距离
- 左右节点到当前节点的距离和（高度和）+1（本节点）
父需要的只是左右节点的高度和，而子的最大距离和父的最大距离无关，也就是子的最大距离路径可能不经过父节点。倒着的V
Info：最大距离，高度
递归：process
3. 代码
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
process
public static Info process(Node x) {
if (x == null) {
return new Info(0, 0);
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
int p1 = leftInfo.maxDistance;
int p2 = rightInfo.maxDistance;
int p3 = leftInfo.height + rightInfo.height + 1;
int maxDistance = Math.max(Math.max(p1, p2), p3);
return new Info(maxDistance, height);
}
5.13 找最大子树是搜索二叉树的数
判断条件：
- 左BST？
- 右BST？
- 左max < x
- 右min > x
- 左size + 右size +1
- 最大的BSTSize
简化一下，可以判断如果对于当前节点来说，最大的BSTSize==自己的size，可以认为是BST，反之则不是
3. 代码
public static class Info {
public int maxBSTSubtreeSize;
public int allSize;
public int max;
public int min;
public Info(int m, int a, int ma, int mi) {
maxBSTSubtreeSize = m;
allSize = a;
max = ma;
min = mi;
}
}
public static Info process(TreeNode x) {
if (x == null) {
return null;
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.val;
int min = x.val;
int allSize = 1;
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
allSize += leftInfo.allSize;
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
allSize += rightInfo.allSize;
}
int p1 = -1;
if (leftInfo != null) {
p1 = leftInfo.maxBSTSubtreeSize;
}
int p2 = -1;
if (rightInfo != null) {
p2 = rightInfo.maxBSTSubtreeSize;
}
int p3 = -1;
boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
if (leftBST && rightBST) {
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (x.val < rightInfo.min);
if (leftMaxLessX && rightMinMoreX) {
int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
p3 = leftSize + rightSize + 1;
}
}
return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
}
5.14 二叉树剪枝
1. 题目
https://leetcode.cn/problems/pOCWxh
给定一个二叉树 根节点 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]
2. 思路
假设中间某个节点可以向子节点提出任意要求，我希望子节点直接给我返回我想要的成型的子树。
那么就需要：
- 将我的左子树变成我想要的样子
- 将我的右子树变成我想要的样子
- 我想要的样子是如果左右为空并且自己为0就让自己为空
3. 代码
public TreeNode pruneTree(TreeNode root) {
if(root == null) return null;
// 遍历节点，判断是否可删除
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if(root.left == null && root.right == null && root.val == 0){
root = null;
}
return root;
}