二叉树算法题汇总

清疚 2022-12-20 03:05 190阅读 0赞

**目录**

[二叉树的遍历][Link 1]

[前序遍历][Link 2]

[中序遍历][Link 3]

[后序遍历][Link 4]

[层次遍历][Link 5]

[基础算法][Link 6]

[求二叉树中的节点个数][Link 7]

[求二叉树的深度（高度）][Link 8]

[求二叉树第k层的节点个数][k]

[求二叉树中叶子节点的个数][Link 9]

[判断两棵二叉树是否相同的树][Link 10]

[判断二叉树是不是平衡二叉树][Link 11]

[求二叉树的镜像][Link 12]

[判断两个二叉树是否互相镜像][Link 13]

[判断是否为二分查找树BST][BST]

--------------------

本文的实例代码基于JAVA编写

首先给出节点的数据结构  
`public class TreeNode {`

1.  `int val;`
2.  `TreeNode left;`
3.  `TreeNode right;`
4.   
5.  `TreeNode(int x) {`
6.  `val = x;`
7.  `}`
8.  `}`

## 二叉树的遍历 ##

### 前序遍历 ###

题目参考LeetCode（144）

**递归解法**：

*  如果二叉树为空，空操作
 *  如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> preorderTraversal(TreeNode root) {`
3.  `if (root != null) {`
4.  `list.add(root.val);`
5.  `if (root.left != null) {`
6.  `preorderTraversal(root.left);`
7.  `}`
8.  `if (root.right != null) {`
9.  `preorderTraversal(root.right);`
10. `}`
11.  
12. `}`
13. `return list;`
14. `}`

**非递归**

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> preorderTraversal(TreeNode root) {`
3.  `Stack<TreeNode> stack = new Stack<>();`
4.  `while (root != null || !stack.isEmpty()) {`
5.  `while (root != null) {`
6.  `list.add(root.val);`
7.  `stack.add(root);`
8.  `root = root.left;`
9.  `}`
10. `if (!stack.isEmpty()) {`
11. `TreeNode node = stack.pop();`
12. `root = node.right;`
13. `}`
14. `}`
15. `return list;`
16. `}`

### 中序遍历 ###

题目参考LeetCode（94）

**递归解法**：

*  如果二叉树为空，空操作
 *  如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> inorderTraversal(TreeNode root) {`
3.  `if (root != null) {`
4.  `if (root.left != null) {`
5.  `inorderTraversal(root.left);`
6.  `}`
7.  `list.add(root.val);`
8.  `if (root.right != null) {`
9.  `inorderTraversal(root.right);`
10. `}`
11. `}`
12. `return list;`
13. `}`

**非递归解法**：用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树。

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> inorderTraversal(TreeNode root) {`
3.  `Stack<TreeNode> stack = new Stack<>();`
4.  `while (root != null || !stack.isEmpty()) {`
5.  `while (root != null) {`
6.  `stack.add(root);`
7.  `root = root.left;`
8.  `}`
9.  `if (!stack.isEmpty()) {`
10. `root = stack.pop();`
11. `list.add(root.val);`
12. `root = root.right;`
13. `}`
14. `}`
15. `return list;`
16. `}`

### 后序遍历 ###

题目参考LeetCode（145）

**递归解法**：

*  如果二叉树为空，空操作
 *  如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> postorderTraversal(TreeNode root) {`
3.  `if (root != null) {`
4.  `if (root.left != null) {`
5.  `postorderTraversal(root.left);`
6.  `}`
7.  `if (root.right != null) {`
8.  `postorderTraversal(root.right);`
9.  `}`
10. `list.add(root.val);`
11. `}`
12. `return list;`
13. `}`

**非递归解法**：双栈法。

1.  `List<Integer> list = new ArrayList<Integer>();`
2.  `public List<Integer> postorderTraversal(TreeNode root) {`
3.  `Stack<TreeNode> stack1 = new Stack<>();`
4.  `Stack<TreeNode> stack2 = new Stack<>();`
5.  `if (root != null) {`
6.  `stack1.add(root);`
7.  `}`
8.  `while (!stack1.isEmpty()) {`
9.  `TreeNode node = stack1.pop();`
10. `stack2.add(node);`
11. `if (node.left != null) {`
12. `stack1.add(node.left);`
13. `}`
14. `if (node.right != null) {`
15. `stack1.add(node.right);`
16. `}`
17. `}`
18. `while (!stack2.isEmpty()) {`
19. `list.add(stack2.pop().val);`
20. `}`
21. `return list;`
22. `}`

### 层次遍历 ###

思路：分层遍历二叉树（按层次从上到下，从左到右）迭代，相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

1.  `public static void levelTraversal(TreeNode root){`
2.  `if(root == null) {`
3.  `return;`
4.  `}`
5.  `Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点`
6.  `queue.add(root);`
7.  `while (!queue.isEmpty()) {`
8.  `TreeNode temp = queue.poll();`
9.  `System.out.print(temp.val + "->");`
10. `if (temp.left != null) { // 添加左右子节点到对列`
11. `queue.add(temp.left);`
12. `}`
13. `if (temp.right != null) {`
14. `queue.add(temp.right);`
15. `}`
16. `}`
17. `}`

变形：按层保存，题目参考LeetCode（102）

1.  `public List<List<Integer>> levelOrder(TreeNode root) {`
2.  `List<List<Integer>> list = new ArrayList<List<Integer>>();`
3.  `Queue<TreeNode> queue = new LinkedList<>();`
4.  `if (root != null) {`
5.  `queue.add(root);`
6.  `}`
7.  `while (!queue.isEmpty()) {`
8.  `int size = queue.size();`
9.  `List<Integer> l = new ArrayList<>();`
10. `while (size > 0) {`
11. `TreeNode node = queue.poll();`
12. `if (node.left != null) {`
13. `queue.add(node.left);`
14. `l.add(node.left.val);`
15. `}`
16. `if (node.right != null) {`
17. `queue.add(node.right);`
18. `l.add(node.right.val);`
19. `}`
20. `size--;`
21. `}`
22. `list.add(l);`
23. `}`
24. `return list;`
25. `}`

## 基础算法 ##

### 求二叉树中的节点个数 ###

**递归解法**： O(n)O(n)

*  如果二叉树为空，节点个数为0
 *  如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

1.  `public static int getNodeNumRec(TreeNode root) {`
2.  `if (root == null) {`
3.  `return 0;`
4.  `}`
5.  `return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;`
6.  `}`

**非递归解法**：O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue，在Java里面可以用LinkedList来模拟

1.  `public static int getNodeNum(TreeNode root) {`
2.  `if (root == null) {`
3.  `return 0;`
4.  `}`
5.  `Queue<TreeNode> queue = new LinkedList<>(); // 用队列保存树节点，先进先出`
6.  `queue.add(root);`
7.  `int count = 1; // 节点数量`
8.  `while (!queue.isEmpty()) {`
9.  `TreeNode temp = queue.poll(); // 每次从对列中删除节点，并返回该节点信息`
10. `if (temp.left != null) { // 添加左子孩子到对列`
11. `queue.add(temp.left);`
12. `count++;`
13. `}`
14. `if (temp.right != null) { // 添加右子孩子到对列`
15. `queue.add(temp.right);`
16. `count++;`
17. `}`
18. `}`
19. `return count;`
20. `}`

### 求二叉树的深度（高度） ###

题目参考LeetCode（104）

**递归解法**： O(n)O(n)

*  如果二叉树为空，二叉树的深度为0
 *  如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

1.  `public int maxDepth(TreeNode root) {`
2.  `int d = 0;`
3.  `if (root == null) {`
4.  `return 0;`
5.  `}`
6.  `d = Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;`
7.  `return d;`
8.  `}`

**非递归解法**：O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue，在Java里面可以用LinkedList来模拟。

1.  `public static int getDepth(TreeNode root) {`
2.  `if (root == null) {`
3.  `return 0;`
4.  `}`
5.  `int currentLevelCount = 1; // 当前层的节点数量`
6.  `int nextLevelCount = 0; // 下一层节点数量`
7.  `int depth = 0; // 树的深度`
8.   
9.  `Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点`
10. `queue.add(root);`
11. `while (!queue.isEmpty()) {`
12. `TreeNode temp = queue.remove(); // 移除节点`
13. `currentLevelCount--; // 当前层节点数减1`
14. `if (temp.left != null) { // 添加左节点并更新下一层节点个数`
15. `queue.add(temp.left);`
16. `nextLevelCount++;`
17. `}`
18. `if (temp.right != null) { // 添加右节点并更新下一层节点个数`
19. `queue.add(temp.right);`
20. `nextLevelCount++;`
21. `}`
22. `if (currentLevelCount == 0) { // 如果是该层的最后一个节点，树的深度加1`
23. `depth++;`
24. `currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下一层节点数量`
25. `nextLevelCount = 0;`
26. `}`
27. `}`
28. `return depth;`
29. `}`

### 求二叉树第k层的节点个数 ###

递归解法： O(n)O(n)  
思路：求以root为根的k层节点数目，等价于求以root左孩子为根的k-1层（因为少了root）节点数目 加上以root右孩子为根的k-1层（因为 少了root）节点数目。即：

如果二叉树为空或者k<1，返回0  
如果二叉树不为空并且k==1，返回1  
如果二叉树不为空且k>1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和

1.  `public static int getNodeNumKthLevelRec(TreeNode root, int k) {`
2.  `if (root == null || k < 1) {`
3.  `return 0;`
4.  `}`
5.  `if (k == 1) {`
6.  `return 1;`
7.  `}`
8.  `return getNodeNumKthLevelRec(root.left, k - 1) + getNodeNumKthLevelRec(root.right, k - 1);`
9.  `}`

### 求二叉树中叶子节点的个数 ###

**递归解法**：

*  如果二叉树为空，返回0
 *  如果二叉树是叶子节点，返回1
 *  如果二叉树不是叶子节点，二叉树的叶子节点数 = 左子树叶子节点数 + 右子树叶子节点数

1.  `public static int getNodeNumLeafRec(TreeNode root) {`
2.  `if (root == null) {`
3.  `return 0;`
4.  `}`
5.  `if (root.left == null && root.right == null) {`
6.  `return 1;`
7.  `}`
8.  `return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);`
9.  `}`

**非递归解法**：基于层次遍历进行求解，利用Queue进行。

1.  `public static int getNodeNumLeaf(TreeNode root){`
2.  `if (root == null) {`
3.  `return 0;`
4.  `}`
5.  `int leaf = 0; // 叶子节点个数`
6.  `Queue<TreeNode> queue = new LinkedList<>();`
7.  `queue.add(root);`
8.  `while (!queue.isEmpty()) {`
9.  `TreeNode temp = queue.poll();`
10. `if (temp.left == null && temp.right == null) { // 叶子节点`
11. `leaf++;`
12. `}`
13. `if (temp.left != null) {`
14. `queue.add(temp.left);`
15. `}`
16. `if (temp.right != null) {`
17. `queue.add(temp.right);`
18. `}`
19. `}`
20. `return leaf;`
21. `}`

### 判断两棵二叉树是否相同的树 ###

**递归解法**：

*  如果两棵二叉树都为空，返回真
 *  如果两棵二叉树一棵为空，另外一棵不为空，返回假
 *  如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假

1.  `public static boolean isSameRec(TreeNode r1, TreeNode r2) {`
2.  `if (r1 == null && r2 == null) { // 都是空`
3.  `return true;`
4.  `} else if (r1 == null || r2 == null) { // 有一个为空，一个不为空`
5.  `return false;`
6.  `}`
7.  `if (r1.val != r2.val) { // 两个不为空，但是值不相同`
8.  `return false;`
9.  `}`
10. `return isSameRec(r1.left, r2.left) && isSameRec(r1.right, r2.right); // 递归遍历左右子节点`
11. `}`

**非递归解法**：利用Stack对两棵树对应位置上的节点进行判断是否相同。

1.  `public static boolean isSame(TreeNode r1, TreeNode r2){`
2.  `if (r1 == null && r2 == null) { // 都是空`
3.  `return true;`
4.  `} else if (r1 == null || r2 == null) { // 有一个为空，一个不为空`
5.  `return false;`
6.  `}`
7.  `Stack<TreeNode> stack1 = new Stack<>();`
8.  `Stack<TreeNode> stack2 = new Stack<>();`
9.  `stack1.add(r1);`
10. `stack2.add(r2);`
11. `while (!stack1.isEmpty() && !stack2.isEmpty()) {`
12. `TreeNode temp1 = stack1.pop();`
13. `TreeNode temp2 = stack2.pop();`
14. `if (temp1 == null && temp2 == null) { // 两个元素都为空，因为添加的时候没有对空节点做判断`
15. `continue;`
16. `} else if (temp1 != null && temp2 != null && temp1.val == temp2.val) {`
17. `stack1.push(temp1.left); // 相等则添加左右子节点判断`
18. `stack1.push(temp1.right);`
19. `stack2.push(temp2.left);`
20. `stack2.push(temp2.right);`
21. `} else {`
22. `return false;`
23. `}`
24. `}`
25. `return true;`
26. `}`

### 判断二叉树是不是平衡二叉树 ###

**递归实现**：借助前面实现好的求二叉树高度的函数

*  如果二叉树为空， 返回真
 *  如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

1.  `public static boolean isAVLTree(TreeNode root) {`
2.  `if (root == null) {`
3.  `return true;`
4.  `}`
5.  `if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) { // 左右子树高度差大于1`
6.  `return false;`
7.  `}`
8.  `return isAVLTree(root.left) && isAVLTree(root.right); // 递归判断左右子树`
9.  `}`

### 求二叉树的镜像 ###

**递归实现**：破坏原来的树，把原来的树改成其镜像

*  如果二叉树为空，返回空
 *  如果二叉树不为空，求左子树和右子树的镜像，然后交换左右子树

1.  `public static TreeNode mirrorRec(TreeNode root) {`
2.  `if (root == null) {`
3.  `return root;`
4.  `}`
5.  `TreeNode left = mirrorRec(root.right); // 递归镜像左右子树`
6.  `TreeNode right = mirrorRec(root.left);`
7.  `root.left = left; // 更新根节点的左右子树为镜像后的树`
8.  `root.right = right;`
9.  `return root;`
10. `}`

**递归实现**：不能破坏原来的树，返回一个新的镜像树

*  如果二叉树为空，返回空
 *  如果二叉树不为空，求左子树和右子树的镜像，然后交换左右子树

1.  `public static TreeNode mirrorCopyRec(TreeNode root) {`
2.  `if (root == null) {`
3.  `return root;`
4.  `}`
5.  `TreeNode newRoot = new TreeNode(root.val); // 创建新节点，然后交换左右子树`
6.  `newRoot.left = mirrorCopyRec(root.right);`
7.  `newRoot.right = mirrorCopyRec(root.left);`
8.  `return newRoot;`
9.  `}`

### 判断两个二叉树是否互相镜像 ###

**递归解法**：与比较两棵二叉树是否相同解法一致（题5），非递归解法省略。

*  比较r1的左子树的镜像是不是r2的右子树
 *  比较r1的右子树的镜像是不是r2的左子树

1.  `public static boolean isMirrorRec(TreeNode r1, TreeNode r2) {`
2.  `if (r1 == null && r2 == null) {`
3.  `return true;`
4.  `} else if (r1 == null || r2 == null) {`
5.  `return false;`
6.  `}`
7.  `if (r1.val != r2.val) {`
8.  `return false;`
9.  `}`
10. `// 递归比较r1的左子树的镜像是不是r2右子树`
11. `// 和r1的右子树的镜像是不是r2的左子树`
12. `return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);`
13. `}`

### 判断是否为二分查找树BST ###

题目参考LeetCode（98）

**递归解法**：中序遍历的结果应该是递增的

1.  `public static boolean isValidBST(TreeNode root, int pre){`
2.  `if (root == null) {`
3.  `return true;`
4.  `}`
5.  `boolean left = isValidBST(root.left, pre);`
6.  `if (!left) {`
7.  `return false;`
8.  `}`
9.  `if(root.val <= pre) {`
10. `return false;`
11. `}`
12. `pre = root.val;`
13. `boolean right = isValidBST(root.right, pre);`
14. `if(!right) {`
15. `return false;`
16. `}`
17. `return true;`
18. `}`

[Link 1]: https://blog.csdn.net/u013967628/article/details/90341129#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
[Link 2]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 3]: https://blog.csdn.net/u013967628/article/details/90341129#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 4]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86
[Link 5]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86
[Link 6]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95
[Link 7]: https://blog.csdn.net/u013967628/article/details/90341129#%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0
[Link 8]: https://blog.csdn.net/u013967628/article/details/90341129#%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6%EF%BC%88%E9%AB%98%E5%BA%A6%EF%BC%89
[k]: https://blog.csdn.net/u013967628/article/details/90341129#%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E7%AC%ACk%E5%B1%82%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0
[Link 9]: https://blog.csdn.net/u013967628/article/details/90341129#%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%8F%B6%E5%AD%90%E8%8A%82%E7%82%B9%E7%9A%84%E4%B8%AA%E6%95%B0
[Link 10]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%88%A4%E6%96%AD%E4%B8%A4%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E7%9B%B8%E5%90%8C%E7%9A%84%E6%A0%91
[Link 11]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%88%A4%E6%96%AD%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E4%B8%8D%E6%98%AF%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91
[Link 12]: https://blog.csdn.net/u013967628/article/details/90341129#%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F
[Link 13]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%88%A4%E6%96%AD%E4%B8%A4%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%BA%92%E7%9B%B8%E9%95%9C%E5%83%8F
[BST]: https://blog.csdn.net/u013967628/article/details/90341129#%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E4%B8%BA%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E6%A0%91BST