算法很美条记（Java）——树（知识点）

目次
性子
树
结构
二叉树
​编辑 ​编辑
结构
遍历
迭代（中序）
 条理遍历（bfs）
二叉树的条理遍历
习题：二叉树中节点最多的层的节点数
二叉查找树（BST）
结构
判断二叉查找树
 BST类里的方法
添加
删除
搜刮
创建
最大值
最小值
contains
某节点的后继
带parent
不带parent
某节点的前驱
某节点高度
均衡二叉树（AVL）
均衡因子
添加
删除
调解均衡
右旋和左旋
带parent的AVL
叶子节点的个数
第k层的节点数
是否是完全二叉树
是否雷同
是否镜像
翻转二叉树（二叉树的镜像）
前序遍历
后序遍历
中序遍历（非递归）
BST区间搜刮
利用bfs实现
利用dfs实现
二叉树套路
判断均衡二叉树
判断完全二叉树

---

性子

树

上面的性子由于两个结点由一条边连成
结点数目越多，算法复杂度越高 

结构

二叉树

 

结构

与树的条理遍历思绪同等，只不外孩子列表明白成了左右孩子

2. // 定义二叉树节点的类
3. class Node {
4.     int val;
5.     Node lchild; // 左子树
6.     Node rchild; // 右子树
8.     // 构造函数，初始化节点的值和子树
9.     Node(int val) {
10.         this.val = val;
11.         this.lchild = null;
12.         this.rchild = null;
13.     }
14. }

复制代码

遍历

先序：根左右
中序：左根右
后序：左右根
以先序为例：
递归（先序）：

下图内里的1、2、3是第反复回到本节点

从递归流程中看：

迭代（先序）：
1、从栈中弹出一个节点
2、打印这个节点
3、按先右后左（假如有）的次序将节点压栈
4、重复上面步调，直到全打印

1. public static void pre(Node head) {
2. //                head是一棵树的头节点
3.                 if(head != null) {
4.                         Stack<Node> stack = new Stack<Node>();
5.                         stack.add(head);
6.                         while(!stack.isEmpty()) {
7. //                                1.
8.                                 Node currNode = stack.pop();
9. //                                2.
10.                                 System.out.print(currNode.val + " ");
11. //                                3.
12.                                 if(currNode.right != null) {
13.                                         stack.push(currNode.right);
14.                                 }
15.                                 if(currNode.left != null) {
16.                                         stack.push(currNode.left);
17.                                 }
18.                         }
19.                 }
20.         }

复制代码

迭代（后序）
1、从栈中弹出一个节点
2、把节点放入备用栈
3、按先左后右（假如有）的次序将节点压栈
4、重复上面步调，直到全压入备用栈
5、打印备用栈

1. public static void posOrderUnRecur1(Node head) {
2.     System.out.print("pos-order: ");
3.     if (head != null) {
4.         Stack<Node> s1 = new Stack<Node>();
5.         Stack<Node> s2 = new Stack<Node>();
6.         s1.push(head);
7.         while (!s1.isEmpty()) {
8.             head = s1.pop();
9.             s2.push(head);
10.             if (head.left != null) {
11.                 s1.push(head.left);
12.             }
13.             if (head.right != null) {
14.                 s1.push(head.right);
15.             }
16.         }
17.         while (!s2.isEmpty()) {
18.             System.out.print(s2.pop().value + " ");
19.         }
20.     }
21.     System.out.println();
22. }

复制代码

迭代（中序）

1、每颗子树整棵树的左孩子全部进栈（下面循环里的if代码）
2、弹出节点
3、打印
4、对其有孩子重复上面操纵

1. public static void inOrderUnRecur(Node head) {
2.     System.out.print("in-order: ");
3.     if (head != null) {
4.         Stack<Node> stack = new Stack<Node>();
5.         while (!stack.isEmpty() || head != null) {
6. //不断将左孩子进栈，移动指针
7.             if (head != null) {
8.                 stack.push(head);
9.                 head = head.left;
10.             } else {
11. //左孩子全进栈了，开始弹出节点
12.                 head = stack.pop();
13. //1、打印
14.                 System.out.print(head.value + " ");
15. //2、将指针移到弹出节点的右孩子上，用循环操作他（有左孩子就进if，没有就进else）
16.                 head = head.right;
17.             }
18.         }
19.     }
20.     System.out.println();
21. }

复制代码

 条理遍历（bfs）

利用队列，弹一个，加N个（队列里弹出一个元素，就把这个元素的全部孩子加进去）
详细来说：指针先指树根，到场队列里后，弹出队列，把他的孩子都到场，再弹，再加
关于树的很多标题都用到了这种遍历，须要对每个结点做处理处罚的，但又不须要按某种门路，比如一条路走到黑，就用层序遍历即可
二叉树的条理遍历

与树的条理遍历思绪同等，只不外孩子列表明白成了左右孩子

1. public void levelOrder(Node root) {
2.         if (root == null) {
3.             return;
4.         }
5.         Queue<Node> contain = new LinkedList<>();
6.         contain.add(root);
7.         Node curr;
8. //        队列不为空就一直处理
9.         while (!contain.isEmpty()) {
10. //            弹出一个
11.             curr = contain.poll();
12.             System.out.println(curr.val + " ");
13. //            添加其孩子
14. //先加左再加右
15.             if (curr.left != null) contain.add(curr.left);
16.             if (curr.right != null) contain.add(curr.right);
17.         }
18.     }

复制代码

习题：二叉树中节点最多的层的节点数

在层序遍历的底子上添加代码来完成
加个hashmap纪录节点的地点层数
每次向栈加新节点的同时，向hashmap纪录这个新节点的层数（当前处理处罚节点地点层数+1）
将当前层数与当前处理处罚节点地点层数做比力，
相当则该节点属于本层，本层总结点数+1
不相当则该节点属于下一层，结算本层数据，行止理处罚下一层

1. public int maxNodesInLevel(Node head) {
2.     if (head == null) {
3.         return 0;
4.     }
5.     Queue<Node> queue = new LinkedList<>();
6.     queue.add(head);
7. //用hashmap记录节点的所在层数
8.     HashMap<Node, Integer> levelMap = new HashMap<>();
9. //头节点层数是1
10.     levelMap.put(head, 1);
11. //当前层数
12.     int curLevel = 1;
13. //当前层数的结点数
14.     int curLevelNodes = 0;
15. //最终所求
16.     int max = Integer.MIN_VALUE;
17.    
18.     while (!queue.isEmpty()) {
19. //从栈中弹出节点
20.         Node cur = queue.poll();、
21. //拿到当前处理节点的层数
22.         int curNodeLevel = levelMap.get(cur);
23. //当前处理节点的层数 与 当前层数一致，则该节点属于当前层，
24.         if (curNodeLevel == curLevel) {
25. //当前层数的结点数+1
26.             curLevelNodes++;
27.         } else {
28. //该节点属于下一层
29. //结算当前层数据
30.             max = Math.max(max, curLevelNodes);
31.             curLevel++;
32. //重置为1
33.             curLevelNodes = 1;
34.         }
35. //当前处理节点的左右孩子节点的层数 是当前处理节点层数+1
36.         if (cur.left != null) {
37.             levelMap.put(cur.left, curNodeLevel + 1);
38.             queue.add(cur.left);
39.         }
40.         if (cur.right != null) {
41.             levelMap.put(cur.right, curNodeLevel + 1);
42.             queue.add(cur.right);
43.         }
44.     }
45.    
46.     // 检查最后一层
47.     max = Math.max(max, curLevelNodes);
48.    
49.     return max;
50. }

复制代码

二叉查找树（BST）

比root小的放左边，大的放右边
中序遍历（左→根→右）可得到严酷递增的节点值序列，这是判断二叉搜刮树的紧张依据
结构

与二叉树雷同

2. // 定义二叉搜索树的类
3. public class BST {
4.     private Node root; // 根节点
5.     private int size;  // 节点个数
7.     // 构造函数，初始化根节点为null
8.     public BST() {
9.         this.root = null;
10.         this.size = 0;
11.     }
13.     // 判断二叉搜索树是否为空
14.     public boolean isEmpty() {
15.         return root == null;
16.     }
18.     // 获取二叉搜索树的节点个数
19.     public int size() {
20.         return size;
21.     }
23.     // 清空二叉搜索树
24.     public void clear() {
25.         this.root = null;
26.     }
27. }

复制代码

判断二叉查找树

中序遍历，是升序的，则是二叉查找树

1. public static int preValue = Integer.MIN_VALUE;
2. public static boolean checkBST(Node head) {
3.     if (head == null) {
4.         return true;
5.     }
6.     boolean isLeftBst = checkBST(head.left);
7.     if (!isLeftBst) {
8.         return false;
9.     }
10.     if (head.value <= preValue) {
11.         return false;
12.     } else {
13.         preValue = head.value;
14.     }
15.     return checkBST(head.right);
16. }

复制代码

 BST类里的方法

只要有修改了树的方法，就会有返回节点，每次返回都要更新树（也就是node.rchild = method(……））
eg
删除（须要改变树）
if (val < root.val) {
            root.lchild = BSTDelete(root.lchild, val);
        } else if (val > root.val) {
            root.rchild = BSTDelete(root.rchild, val);
        } else {
添加（须要改变树）
if (val < node.val) {
            node.lchild = addNode(node.lchild, val);
        } else if (val > node.val) {
            node.rchild = addNode(node.rchild, val);
        }
搜刮（不须要改变树）
} else if (val < root.val) {
            return BSTSearch(root.lchild, val);
        } else {
            return BSTSearch(root.rchild, val);
添加

都添加成树叶，不会在中央添加

1. // 添加节点的方法
2.     public void addNode(int val) {
3.         this.root = addNode(this.root, val);
4.         this.size++;
5.     }
7.     // 递归插入节点的方法
8.     private Node addNode(Node node, int val) {
9.         if (node == null) {
10.             return new Node(val);
11.         }
12.         if (val < node.val) {
13.             node.lchild = addNode(node.lchild, val);
14.         } else if (val > node.val) {
15.             node.rchild = addNode(node.rchild, val);
16.         }
17.         return node;
18.     }

复制代码

删除

须要思量三种情况：

• 要删除的节点是叶子节点：直接删除该节点。
  
• 要删除的节点只有一个子节点：用该子节点更换要删除的节点。
  
• 要删除的节点有两个子节点：找到该节点右子树中的最末节点（即右子树中最左边的节点），用这个最末节点的值更换要删除节点的值，然后删除右子树中的最末节点。
  

1. public void BSTDelete(int val) {
2.         int originalSize = this.size;
3.         this.root = BSTDelete(this.root, val);
4. //因为会有树为空，删除失败的情况，所以不能直接size--
5.         if (originalSize > this.size) {
6.             this.size--;
7.         }
8.     }
10. public Node BSTDelete(Node root, int val) {
11.         if (root == null) {
12.             return null;
13.         }
14. // 递归地在左子树中查找要删除的节点
15.         if (val < root.val) {
16.             root.lchild = BSTDelete(root.lchild, val);
17.         } else if (val > root.val) {
18. // 递归地在右子树中查找要删除的节点
19.             root.rchild = BSTDelete(root.rchild, val);
20.         }
21. // 找到要删除的节点
22.         else {
23.             // 情况 1: 要删除的节点没有子节点或只有一个子节点
24.             if (root.lchild == null) {
25.                 return root.rchild;
26.             } else if (root.rchild == null) {
27.                 return root.lchild;
28.             }
29.             // 情况 2: 要删除的节点有两个子节点
30.             // 找到右子树中的最小节点
31.             root.val = Min(root.rchild);
32.             // 删除右子树中的最小节点
33.             root.rchild = BSTDelete(root.rchild, root.val);
34.         }
35.         return root;
36.     }

复制代码

搜刮

1. public Node BSTSearch(Node root, int val) {
2.         if (root == null) {
3.             return null;
4.         }
5.         if (val == root.val) {
6.             return root;
7.         } else if (val < root.val) {
8.             return BSTSearch(root.lchild, val);
9.         } else {
10.             return BSTSearch(root.rchild, val);
11.         }
12.     }

复制代码

创建

这里没有维护size

1. public Node BSTBuild(int[] nums) {
2.         if (nums == null || nums.length == 0) {
3.             return null;
4.         }
5.         this.root = new Node(nums[0]);
6.         for (int i = 1; i < nums.length; i++) {
7.             addNode(nums[i]);
8.         }
9.         return this.root;
10.     }

复制代码

最大值

最右边的值最大
以是我们可以用一个指针p指向root，而后不绝移动指针，直到p.right == null
大概用递归

1.     //    找最大,树的最右节点
2.     public int Max(){
3.         if (root == null){
4.             return -100000;
5.         }
6.         Node node = findMax(root);
7.         return node.val;
8.     }
9.     private Node findMax(Node root){
10.         if(root.right == null){
11.             return root;
12.         }
13.         return findMax(root.right);
14.     }

复制代码

最小值

最左边的值最小
同上220-年事 60-80

1.     //    找最小，树的最左节点
2.     public int Min(){
3.         if (root == null){
4.             return 100000;
5.         }
6.         Node node = findMin(root);
7.         return node.val;
8.     }
9.     private Node findMin(Node root){
10.         if(root.left == null){
11.             return root;
12.         }
13.         return findMin(root.left);
14.     }

复制代码

contains

1.   
3.     public boolean contains(TreeNode root, int val) {
4.         if(root == null){
5.             return false;
6.         }
7.         if(root.val == val){
8.             return true;
9.         } else if (root.val > val) {
10.             return contains(root.left,val);
11.         } else {
12.             return contains(root.right,val);
13.         }
14.     }

复制代码

某节点的后继

指的是中序遍历后的谁人序列，某节点的后继
就是比这个节点大的第一个节点
两种情况：1、是其右子树的最小值
                  2、没有右子树，则向上追溯，直到某个先人节点是左孩子，那么这个先人节点的父节点就是所求（也就是：后继节点是末了一个比目的节点值大的先人节点）
带parent

1. public static Node findSuccessor(Node node) {
2.         if (node == null) {
3.             return null;
4.         }
6.         // 情况 1：节点有右子树
7.         if (node.right != null) {
8.             return findMin(node.right); // 找到右子树中的最左节点
9.         }
11.         // 情况 2：节点没有右子树
12.         Node current = node;
13.         Node parent = current.parent;
14.         while (parent != null && current == parent.right) {
15.             current = parent;
16.             parent = parent.parent;
17.         }
18.         return parent;
19.     }

复制代码

不带parent

思绪一样，只是不找第一个左孩子了，而是用括号里的规则：后继节点是末了一个比目的节点值大的先人节点
意思是，假如按原来的思绪，向上回溯找第一个左孩子，而假如从上到下找，则找的是末了一个但不凌驾目的节点的谁人节点（假如凌驾目的节点了，就不符合追溯（第一个）的思绪了
由于没有parent，不能从下到上，只能从上到下，以是要传一个root

1. public static Node findSuccessor(Node root, Node target) {
2.         if (root == null || target == null) {
3.             return null;
4.         }
6.         // 情况 1：目标节点有右子树
7.         if (target.right != null) {
8.             return findMin(target.right); // 找到右子树中的最左节点
9.         }
11.         // 情况 2：目标节点没有右子树
12. //        successor是后继
13.         Node successor = null;
14.         Node curr = root;
15. //        一直找，直到curr指向目标节点就停止（也就是把目标节点上面的元素都处理一遍）
16.         while (curr != null) {
17.             if (curr.val > target.val) {
18.                 successor = curr; // 当前节点可能是后继节点
19.                 curr = curr.left; // 继续向左子树查找更小的值
20.             } else if (curr.val < target.val) {
21.                 curr = curr.right; // 继续向右子树查找
22.             } else {
23. //                curr指向目标节点，停止
24.                 break; // 找到目标节点，退出循环
25.             }
26.         }
27.         return successor;
28.     }

复制代码

某节点的前驱

指的是中序遍历后的谁人序列，某节点的前驱
就是比这个节点小的第一个节点
两种情况：1、是其左子树的最大值
                  2、没有左子树，则向上追溯，直到某个先人节点是右孩子，那么这个先人节点的父节点就是所求
这道题TreeNode带parent
代码参考：某节点的后继
某节点高度

当前节点到叶子节点的最长路径长度
递归得到左右子树的高度，取较高的一方+1就是某节点的高度

1. public int getHeight(Node node) {
2.         if (node == null) return 0;
3.         int l = getHeight(node.left);
4.         int r = getHeight(node.right);
5.         return 1 + Math.max(l, r);
6.     }

复制代码

均衡二叉树（AVL）

左右子树的高度差（均衡因子）不大于1
AVL也是BST，只不外多了一个高度差的特点，以是根本操纵实现思绪按BST举行就行，同时思量差别点即可，这里，我们直接复用BST的操纵
均衡因子

1. public int getHeight(Node node) {
2.         if (node == null) return 0;
3.         return 1 + Math.max(getHeight(node.lchild), getHeight(node.rchild));
4.     }
5. public int getBalanceFactor(Node node) {
6.         if (node == null) {
7.             return 0;
8.         }
9.         int leftHeight = getHeight(node.left);
10.         int rightHeight = getHeight(node.right);
11.         return leftHeight - rightHeight;
12.     }

复制代码

假如节点结构里有height，则可以直接调用：
但是假如这个节点是改变后的，想要更新height，就只能用上面的，不能用下面这个方法（纪录过的height）

1.    //获取当前节点的高度
2.     public int getHeight(Node node){
3.         if (node==null){
4.             return 0;
5.         }
6.         return node.height;
7.     }
8.     //获取当前节点的平衡因子
9.     public int getBalanceFactor(Node node){
10.         if (node==null){
11.             return 0;
12.         }
13.         return getHeight(node.left)-getHeight(node.right);
14.     }

复制代码

添加

先复用BST的插入，再调解均衡

1. // AVL 插入操作
2.     public void insert(int val) {
3.         root = bstInsert(root, val);
4.         root = balanceTree(root);
5.     }

复制代码

删除

2.     // AVL 删除操作
3.     public void delete(int val) {
4.         root = bstDelete(root, val);
5.         root = balanceTree(root);
6.     }

复制代码

调解均衡

判断不均衡范例的关键在于当前不均衡节点（均衡因子为 -2 或 2 的节点）及其子节点的均衡因子。
1.LL 型

• 判断条件：当前不均衡节点的均衡因子为 2，且其左子节点的均衡因子为 1。
  
• 调解方法：右旋
  

2. LR 型

• 判断条件：当前不均衡节点的均衡因子为 2，且其左子节点的均衡因子为 -1。
  
• 调解方法：左旋+右旋
  

3. RR 型

• 判断条件：当前不均衡节点的均衡因子为 -2，且其右子节点的均衡因子为 -1。
  
• 调解方法：左旋
  

4. RL 型

• 判断条件：当前不均衡节点的均衡因子为 -2，且其右子节点的均衡因子为 1。
  
• 调解方法：右旋+左旋
  

查抄每个节点（用递归来实现）是否均衡，不均衡就调解 

1. / 调整树的平衡
2.     public Node balanceTree(Node node) {
3.         if (node == null) {
4.             return node;
5.         }
6.         node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
7.         int balance = getBalanceFactor(node);
8.         // LL 型
9.         if (balance > 1 && getBalanceFactor(node.left) >= 0) {
10.             return rightRotate(node);
11.         }
12.         // LR 型
13.         if (balance > 1 && getBalanceFactor(node.left) < 0) {
14.             node.left = leftRotate(node.left);
15.             return rightRotate(node);
16.         }
17.         // RR 型
18.         if (balance < -1 && getBalanceFactor(node.right) <= 0) {
19.             return leftRotate(node);
20.         }
21.         // RL 型
22.         if (balance < -1 && getBalanceFactor(node.right) > 0) {
23.             node.right = rightRotate(node.right);
24.             return leftRotate(node);
25.         }
26.         return node;
27.     }

复制代码

右旋和左旋

1. // 右旋操作
2.     private Node rightRotate(Node y) {
3. //        实际上就是x和y的位置要改变，
4. //        让x成为y的父节点
5. //        没改变前y是x的父节点
6.         Node x = y.left;
7. //        如果有T2，就连给y，没有的话T2就是null，y的左孩子就是null
8.         Node T2 = x.right;
10.         x.right = y;
11.         y.left = T2;
12. //      更新高度
13.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
14.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
16.         return x;
17.     }
19.     // 左旋操作
20.     private Node leftRotate(Node x) {
21.         Node y = x.right;
22.         Node T2 = y.left;
24.         y.left = x;
25.         x.right = T2;
27.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
28.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
30.         return y;
31.     }

复制代码

带parent的AVL

方法详细实现看这篇文章：https://blog.csdn.net/jarvan5/article/details/112428036
叶子节点的个数

1. public int count(Node root) {
2.         if (root == null) {
3.             return 0;
4.         } else if (root.left == null && root.right == null) {
5.             return 1;
6.         }
7.         return count(root.left) + count((root.right));
8.     }

复制代码

第k层的节点数

一个节点的孩子节点的上一层就是这个节点地点层
以是盘算第k层全部节点的孩子节点的上一层结点数，即为所求

1. public int countK(Node root,int k) {
2.         if (root == null) {
3.             return 0;
4.         }
5.         if(k == 1) {
6.             return 1;
7.         }
8.         return countK(root.left , k-1) + countK(root.right , k-1);
9.     }

复制代码

是否是完全二叉树

利用层序遍历，在此底子上，对每次拿到的节点做处理处罚
层序遍历的每个节点：
①、左孩子为空，右孩子不为空的情况，则不是完全二叉树
②、假如背面的节点都应该是叶子节点，但是又有左孩子或右孩子，则不是完全二叉树
以是要维护一个变量，用于体现是否背面的节点都应该是叶子节点
思绪鉴戒：原文链接：https://blog.csdn.net/Hellowenpan/article/details/116700476

1. public boolean isCompleteTree(Node root) {
2.         if (root == null) {
3.             return true;
4.         }
5.         // 从当前节点开始，后面的节点是否都需要是叶子节点
6.         boolean isLeafNode = false;
7.         Queue<Node> contain = new LinkedList<>();
8.         contain.add(root);
9.         Node curr;
10. //        队列不为空就一直处理
11.         while (!contain.isEmpty()) {
12. //            弹出一个
13.             curr = contain.poll();
14.             // ①、左孩子为空，右孩子不为空的情况，直接返回false
15.             if (curr.right != null && curr.left == null) {
16.                 return false;
17.             }
18.             // ②、如果后面的节点都应该是叶子节点，但是又有左孩子或右孩子，则直接返回false
19.             if (isLeafNode && (curr.left != null || curr.right != null)) {
20.                 return false;
21.             }
22.             // ③、遇到第一个左右孩子不双全的节点，那么该节点后的所有节点都应该是叶子节点
23.             if (curr.left == null || curr.right == null) {
24.                 isLeafNode = true;
25.             }
27.             // 压入左孩子到队列
28.             if (curr.left != null) {
29.                 contain.add(curr.left);
30.             }
31.             // 压入右孩子到队列
32.             if (curr.right != null) {
33.                 contain.add(curr.right);
34.             }
35.         }
36.         return true;
37.     }

复制代码

是否雷同

要判断两棵树是否雷同，必须同时满意以下两个条件：

• 结构雷同：两棵树的节点位置和父子关系必须同等。
  
• 节点值雷同：对应位置的节点值必须相当。
  

递归

1. public boolean isSameTree(Node p, Node q) {
2.         // 如果两个节点都为空，则相同
3.         if (p == null && q == null) {
4.             return true;
5.         }
6.         // 如果一个节点为空，另一个不为空，则不同
7.         if (p == null || q == null) {
8.             return false;
9.         }
10.         // 比较当前节点的值
11.         if (p.val != q.val) {
12.             return false;
13.         }
14.         // 递归比较左右子树
15.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
16.     }

复制代码

迭代

1. public boolean isSameTree(Node p, Node q) {
2.         // 使用栈来存储需要比较的节点对
3.         Stack<Node[]> stack = new Stack<>();
4.         stack.push(new Node[]{p, q});
6.         while (!stack.isEmpty()) {
7.             Node[] nodes = stack.pop();
8.             Node node1 = nodes[0];
9.             Node node2 = nodes[1];
11.             // 如果两个节点都为空，继续比较下一对节点
12.             if (node1 == null && node2 == null) {
13.                 continue;
14.             }
15.             // 如果一个节点为空，另一个不为空，则不同
16.             if (node1 == null || node2 == null) {
17.                 return false;
18.             }
19.             // 比较当前节点的值
20.             if (node1.val != node2.val) {
21.                 return false;
22.             }
23.             // 将左右子节点对压入栈中
24.             stack.push(new Node[]{node1.left, node2.left});
25.             stack.push(new Node[]{node1.right, node2.right});
26.         }
28.         return true;
29.     }

复制代码

注意：
中序遍历的结果不能唯一确定一棵树的结构，因此不能直接用来判断两棵树是否雷同
反例

但中序遍历搭配前序大概后序遍历，即可唯一确定一棵树
以是可以比力两种遍历的结果是否同等，同等就雷同
但如许须要开辟空间存遍历结果，以是这种方法不太好（List<Integer>存结果，return pPreOrder.equals(qPreOrder) && pInOrder.equals(qInOrder); 比力）
存结果
是否镜像

判断雷同是left和left比，right和right比
判断镜像是left和right比，right和left比

1. public boolean isMirrorTree(Node p, Node q) {
2.     // 如果两个节点都为空，则相同
3.     if (p == null && q == null) {
4.         return true;
5.     }
6.     // 如果一个节点为空，另一个不为空，则不同
7.     if (p == null || q == null) {
8.         return false;
9.     }
10.     // 比较当前节点的值
11.     if (p.val != q.val) {
12.         return false;
13.     }
14.     // 递归比较左右子树
15.     return isMirrorTree(p.left, q.right) && isMirrorTree(p.right, q.left);
16. }

复制代码

翻转二叉树（二叉树的镜像）

左右反转二叉树的节点

1. public Node reverseTree(Node root) {
2. //        从下到上翻转
3.         if (root == null) {
4.             return null;
5.         }
6.         // 交换当前节点的左右子节点
7.         Node temp = root.left;
8.         root.left = root.right;
9.         root.right = temp;
11.         // 递归地反转左子树
12.         reverseTree(root.left);
13.         // 递归地反转右子树
14.         reverseTree(root.right);
16.         return root;
18.     }

复制代码

前序遍历

1. public void pre(Node root) {
2.         if (root == null) {
3.             return;
4.         }
5.         System.out.print(root.val + " ");
6.         pre(root.left);
7.         pre(root.right);
8.     }

复制代码

后序遍历

1. public void post(Node root) {
2.         if (root == null) {
3.             return;
4.         }
5.         post(root.left);
6.         post(root.right);
7.         System.out.print(root.val + " ");
8.     }

复制代码

中序遍历（非递归）

利用栈
用一个指针curr指向当前处理处罚节点
1、把左孩子全加进去，然后开始出栈，
2、出一个节点就查抄他有没有右孩子，
有就将curr指向右孩子，重复1、2动作

1. public static void inOrder(Node root) {
2.         Node curr = root;
3.         Stack<Node> contain = new Stack<>();
4.         while (curr != null || !contain.isEmpty()) {
5. //                把所有的左孩子都加入
6.             while (curr != null) {
7.                  contain.push(curr);
8.                  curr = curr.left;
9.             }
10.             Node t = contain.pop();
11.             System.out.println(t.val);
12.             if (t.right != null) {
13.                 curr = t.right;
14.             }
15.         }
16.     }

复制代码

BST区间搜刮

给定一个区间范围，输出全部在这个区间的值
利用bfs实现

遍历到每一个节点，判断在不在区间中

1. public void IntervalSearch(Node root,int low,int high) {
2.         if (root == null) {
3.             return;
4.         }
5.         Queue<Node> contain = new LinkedList<>();
6.         contain.add(root);
7.         Node curr;
8. //        队列不为空就一直处理
9.         while (!contain.isEmpty()) {
10. //            弹出一个
11.             curr = contain.poll();
12.             if (curr.val >= low && curr.val <= high) System.out.println(curr.val + " ");
13. //            添加其孩子
14.             if (curr.left != null) contain.add(curr.left);
15.             if (curr.right != null) contain.add(curr.right);
16.         }
17.     }

复制代码

利用dfs实现

分别处理处罚左子树，当前节点和右子树

1. public void IntervalSearch(Node root, int low, int high) {
2.         // 递归终止条件：如果当前节点为空，直接返回
3.         if (root == null) {
4.             return;
5.         }
6. //        找一个条件，使程序需要遍历左子树
7. //        由于：
8.         // 如果当前节点的值大于 low，左子树中才可能存在满足条件的节点，递归遍历左子树
9.         //如果<=low，则左子树中不存在满足条件的节点，不用遍历左子树
10. //        所以条件是root.val > low
11.         if (root.val > low) {
12.             IntervalSearch(root.left, low, high);
13.         }
14.         // 如果当前节点的值在 [low, high] 范围内，则输出该节点的值
15.         if (root.val >= low && root.val <= high) {
16.             System.out.print(root.val + " ");
17.         }
18. //        找一个条件，使程序需要遍历右子树
19. //        剩余思路同上
20.         if (root.val < high) {
21.             IntervalSearch(root.right, low, high);
22.         }
23.     }

复制代码

二叉树套路

向左孩子要信息，向右孩子要信息，举行处理处罚
信息假如不止一个，直接封装成类
假如要的信息不一样，直接全封装成类（叱责集）
判断均衡二叉树

左孩子是否是均衡二叉树，高度是？，右孩子是否是均衡二叉树，高度是？

1. //处理信息的
2. public static boolean isBalanced(Node head) {
3.     return process(head).isBalanced;
4. }
6. public static class ReturnType {
7.     public boolean isBalanced;
8.     public int height;
10.     public ReturnType(boolean isB, int hei) {
11.         isBalanced = isB;
12.         height = hei;
13.     }
14. }
15. //收集信息的
16. public static ReturnType process(Node x) {
17.     if (x == null) {
18.         return new ReturnType(true, 0);
19.     }
20. //得到左右孩子信息（ReturnType）
21.     ReturnType leftData = process(x.left);
22.     ReturnType rightData = process(x.right);
23. //得到自己的信息（ReturnType）
24.     int height = Math.max(leftData.height, rightData.height) + 1;
25.     boolean isBalanced = leftData.isBalanced && rightData.isBalanced
26.             && Math.abs(leftData.height - rightData.height) < 2;
27.     return new ReturnType(isBalanced, height);
28. }

复制代码

判断完全二叉树

层序遍历，查抄左右孩子
1、有右孩子没左孩子，return false
1满意时：2、碰到第一个孩子不双全时，接下来的节点都得是叶子节点（没孩子）