数据结构与算法-二叉树

前序遍历二叉树-Leetcode 144

   给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
  
  示例 1：
  输入：root = [1,null,2,3]
  输出：[1,2,3]
  解释：
  
  

  示例 2：
  输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
  输出：[1,2,4,5,6,7,3,8,9]
  解释：
  
  

  示例 3：
  输入：root = []
  输出：[]
  示例 4：
  输入：root = [1]
  输出：[1]

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 前序遍历二叉树的方法。
20.      * 前序遍历顺序：访问根节点 -> 遍历左子树 -> 遍历右子树
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回前序遍历的结果列表
24.      */
25.     public List<Integer> preorderTraversal(TreeNode root) {
26.         List<Integer> result = new ArrayList<Integer>();  // 存储前序遍历结果的列表
27.         preorder(root, result);  // 调用递归方法进行前序遍历
28.         return result;  // 返回前序遍历的结果
29.     }
31.     /**
32.      * 递归实现前序遍历。
33.      *
34.      * @param node 当前处理的节点
35.      * @param result 用于存储遍历结果的列表
36.      */
37.     private void preorder(TreeNode node, List<Integer> result) {
38.         if (node == null) {  // 如果当前节点为空，直接返回
39.             return;
40.         }
41.         result.add(node.val);  // 将当前节点的值添加到结果列表中（访问根节点）
42.         preorder(node.left, result);  // 递归遍历左子树
43.         preorder(node.right, result);  // 递归遍历右子树
44.     }
45. }

复制代码

中序遍历二叉树-Leetcode 94

   给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
  
  示例 1：
  

1. <strong>输入：</strong>root = [1,null,2,3]
2. <strong>输出：</strong>[1,3,2]

复制代码

示例 2：

1. <strong>输入：</strong>root = []
2. <strong>输出：</strong>[]

复制代码

示例 3：

1. <strong>输入：</strong>root = [1]
2. <strong>输出：</strong>[1]

复制代码

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 中序遍历二叉树的方法。
20.      * 中序遍历顺序：遍历左子树 -> 访问根节点 -> 遍历右子树
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回中序遍历的结果列表
24.      */
25.     public List<Integer> inorderTraversal(TreeNode root) {
26.         List<Integer> result = new ArrayList<Integer>();  // 存储中序遍历结果的列表
27.         inorder(root, result);  // 调用递归方法进行中序遍历
28.         return result;  // 返回中序遍历的结果
29.     }
31.     /**
32.      * 递归实现中序遍历。
33.      *
34.      * @param node 当前处理的节点
35.      * @param result 用于存储遍历结果的列表
36.      */
37.     private void inorder(TreeNode node, List<Integer> result) {
38.         if (node == null) {  // 如果当前节点为空，直接返回
39.             return;
40.         }
42.         inorder(node.left, result);  // 递归遍历左子树
43.         result.add(node.val);  // 将当前节点的值添加到结果列表中（访问根节点）
44.         inorder(node.right, result);  // 递归遍历右子树
45.     }
46. }

复制代码

后序遍历二叉树-Leetcode 145

   给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
  
  示例 1：
  输入：root = [1,null,2,3]
  输出：[3,2,1]
  解释：
  

  示例 2：
  输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
  输出：[4,6,7,5,2,9,8,3,1]
  解释：
  

  示例 3：
  输入：root = []
  输出：[]
  示例 4：
  输入：root = [1]
  输出：[1]
  

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 后序遍历二叉树的方法。
20.      * 后序遍历顺序：遍历左子树 -> 遍历右子树 -> 访问根节点
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回后序遍历的结果列表
24.      */
25.     public List<Integer> postorderTraversal(TreeNode root) {
26.         List<Integer> result = new ArrayList<Integer>();  // 存储后序遍历结果的列表
27.         postorder(root, result);  // 调用递归方法进行后序遍历
28.         return result;  // 返回后序遍历的结果
29.     }
31.     /**
32.      * 递归实现后序遍历。
33.      *
34.      * @param node 当前处理的节点
35.      * @param result 用于存储遍历结果的列表
36.      */
37.     private void postorder(TreeNode node, List<Integer> result) {
38.         if (node == null) {  // 如果当前节点为空，直接返回
39.             return;
40.         }
42.         postorder(node.left, result);  // 递归遍历左子树
43.         postorder(node.right, result);  // 递归遍历右子树
44.         result.add(node.val);  // 将当前节点的值添加到结果列表中（访问根节点）
45.     }
46. }

复制代码

对称二叉树-Leetcode 101

   给你一个二叉树的根节点 root ， 检查它是否轴对称。
  
  示例 1：
  

1. <strong>输入：</strong>root = [1,2,2,3,4,4,3]
2. <strong>输出：</strong>true

复制代码

示例 2：
  

1. <strong>输入：</strong>root = [1,2,2,null,3,null,3]
2. <strong>输出：</strong>false

复制代码

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 检查二叉树是否对称。
20.      * 对称的定义是：左子树和右子树互为镜像。
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 如果树是对称的返回 true，否则返回 false
24.      */
25.     public boolean isSymmetric(TreeNode root) {
26.         // 如果根节点为空，则认为是对称的
27.         if (root == null) {
28.             return true;
29.         }
30.         // 检查根节点的左子树和右子树是否对称
31.         return check(root.left, root.right);
32.     }
34.     /**
35.      * 递归检查两个子树是否互为镜像。
36.      *
37.      * @param left 当前处理的左子树的根节点
38.      * @param right 当前处理的右子树的根节点
39.      * @return 如果两棵子树互为镜像返回 true，否则返回 false
40.      */
41.     public boolean check(TreeNode left, TreeNode right) {
42.         // 如果两个节点都为空，则它们是对称的
43.         if (left == null && right == null) {
44.             return true;
45.         }
46.         // 如果其中一个节点为空而另一个不为空，则它们不对称
47.         if (left == null || right == null) {
48.             return false;
49.         }
50.         // 如果两个节点的值不同，则它们不对称
51.         if (left.val != right.val) {
52.             return false;
53.         }
54.         // 递归检查：
55.         // 左子树的左子节点和右子树的右子节点是否对称
56.         // 左子树的右子节点和右子树的左子节点是否对称
57.         return check(left.left, right.right) && check(left.right, right.left);
58.     }
59. }

复制代码

二叉树最大深度-Leetcode 104

   给定一个二叉树 root ，返回其最大深度。
  二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
  
  示例 1：
  
  

  

1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
2. <strong>输出：</strong>3

复制代码

示例 2：

1. <strong>输入：</strong>root = [1,null,2]
2. <strong>输出：</strong>2

复制代码

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 计算二叉树的最大深度。
20.      * 最大深度是从根节点到最远叶子节点的最长路径上的节点数。
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回二叉树的最大深度
24.      */
25.     public int maxDepth(TreeNode root) {
26.         // 如果当前节点为空，返回深度为0
27.         if (root == null) {
28.             return 0;
29.         }
31.         // 递归计算左子树的最大深度
32.         int leftDepth = maxDepth(root.left);
34.         // 递归计算右子树的最大深度
35.         int rightDepth = maxDepth(root.right);
37.         // 当前节点的深度为其左右子树最大深度加1（加上当前节点自身）
38.         return Math.max(leftDepth, rightDepth) + 1;
39.     }
40. }

复制代码

二叉树最小深度-Leetcode 111

   给定一个二叉树，找出其最小深度。
  最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
  说明：叶子节点是指没有子节点的节点。
  
  示例 1：
  

1. <strong>输入：</strong>root = [3,9,20,null,null,15,7]
2. <strong>输出：</strong>2

复制代码

示例 2：

1. <strong>输入：</strong>root = [2,null,3,null,4,null,5,null,6]
2. <strong>输出：</strong>5

复制代码

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 计算二叉树的最小深度。
20.      * 最小深度是从根节点到最近的叶子节点的最短路径上的节点数。
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回二叉树的最小深度
24.      */
25.     public int minDepth(TreeNode root) {
26.         // 如果当前节点为空，返回深度为0
27.         if (root == null) {
28.             return 0;
29.         }
31.         // 递归计算左子树的最小深度
32.         int leftDepth = minDepth(root.left);
34.         // 递归计算右子树的最小深度
35.         int rightDepth = minDepth(root.right);
37.         // 如果左子树或右子树有一个为空，则返回非空子树的深度加1
38.         // 否则返回左右子树中较小的深度加1
39.         if (leftDepth == 0 && rightDepth == 0) {
40.             return 1; // 当前节点是叶子节点
41.         } else if (leftDepth == 0) {
42.             return rightDepth + 1;
43.         } else if (rightDepth == 0) {
44.             return leftDepth + 1;
45.         } else {
46.             return Math.min(leftDepth, rightDepth) + 1;
47.         }
48.     }
49. }

复制代码

翻转二叉树-Leetcode 226

   给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
  
  示例 1：
  
  

1. <strong>输入：</strong>root = [4,2,7,1,3,6,9]
2. <strong>输出：</strong>[4,7,2,9,6,3,1]

复制代码

示例 2：
  
  

1. <strong>输入：</strong>root = [2,1,3]
2. <strong>输出：</strong>[2,3,1]

复制代码

示例 3：

1. <strong>输入：</strong>root = []
2. <strong>输出：</strong>[]

复制代码

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;  // 节点的值
5. *     TreeNode left;  // 左子节点
6. *     TreeNode right;  // 右子节点
7. *     TreeNode() {}  // 默认构造函数
8. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     /**
19.      * 翻转二叉树。
20.      * 对于每个节点，交换其左子树和右子树。
21.      *
22.      * @param root 二叉树的根节点
23.      * @return 返回翻转后的二叉树的根节点
24.      */
25.     public TreeNode invertTree(TreeNode root) {
26.         // 如果当前节点为空，直接返回 null
27.         if (root == null) {
28.             return null;
29.         }
31.         // 递归翻转左子树
32.         TreeNode left = invertTree(root.left);
34.         // 递归翻转右子树
35.         TreeNode right = invertTree(root.right);
37.         // 交换当前节点的左子树和右子树
38.         TreeNode temp = root.left;
39.         root.left = root.right;
40.         root.right = temp;
42.         // 返回当前节点（翻转后的子树的根节点）
43.         return root;
44.     }
45. }

复制代码

根据前序与中序遍历结果构造二叉树-Leetcode 105

   给定两个整数数组 preorder 和 inorder ，此中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
  
  示例 1:
  

1. <strong>输入</strong><strong>:</strong> preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
2. <strong>输出:</strong> [3,9,20,null,null,15,7]

复制代码

示例 2:

1. <strong>输入:</strong> preorder = [-1], inorder = [-1]
2. <strong>输出:</strong> [-1]

复制代码

1. import java.util.Arrays;
3. /**
4. * Definition for a binary tree node.
5. * public class TreeNode {
6. *     int val;  // 节点的值
7. *     TreeNode left;  // 左子节点
8. *     TreeNode right;  // 右子节点
9. *     TreeNode() {}  // 默认构造函数
10. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     }
16. * }
17. */
18. class Solution {
20.     /**
21.      * 根据前序遍历和中序遍历数组重建二叉树。
22.      *
23.      * @param preorder 前序遍历数组
24.      * @param inorder 中序遍历数组
25.      * @return 返回重建后的二叉树的根节点
26.      */
27.     public TreeNode buildTree(int[] preorder, int[] inorder) {
28.         // 如果前序遍历数组为空，返回 null
29.         if (preorder.length == 0) {
30.             return null;
31.         }
33.         // 获取根节点的值（前序遍历的第一个元素）
34.         int rootValue = preorder[0];
35.         TreeNode root = new TreeNode(rootValue);
37.         // 在中序遍历数组中找到根节点的位置
38.         for (int i = 0; i < inorder.length; i++) {
39.             if (inorder[i] == rootValue) {
40.                 // 分割中序遍历数组为左子树和右子树部分
41.                 int[] inLeft = Arrays.copyOfRange(inorder, 0, i);
42.                 int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
44.                 // 分割前序遍历数组为左子树和右子树部分
45.                 int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
46.                 int[] preRight = Arrays.copyOfRange(preorder, i + 1, inorder.length);
48.                 // 递归构建左子树和右子树
49.                 root.left = buildTree(preLeft, inLeft);
50.                 root.right = buildTree(preRight, inRight);
52.                 break;  // 找到根节点后跳出循环
53.             }
54.         }
56.         // 返回重建后的根节点
57.         return root;
58.     }
59. }

复制代码

根据中序与后序遍历结果构造二叉树-Leetcode 106

   给定两个整数数组 inorder 和 postorder ，此中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
  
  示例 1:
  

1. <strong>输入：</strong>inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
2. <strong>输出：</strong>[3,9,20,null,null,15,7]

复制代码

示例 2:

1. <strong>输入：</strong>inorder = [-1], postorder = [-1]
2. <strong>输出：</strong>[-1]

复制代码

1. import java.util.Arrays;
3. /**
4. * Definition for a binary tree node.
5. * public class TreeNode {
6. *     int val;  // 节点的值
7. *     TreeNode left;  // 左子节点
8. *     TreeNode right;  // 右子节点
9. *     TreeNode() {}  // 默认构造函数
10. *     TreeNode(int val) { this.val = val; }  // 使用给定值初始化节点
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     }
16. * }
17. */
18. class Solution {
20.     /**
21.      * 根据中序遍历和后序遍历数组重建二叉树。
22.      *
23.      * @param inorder 中序遍历数组
24.      * @param postorder 后序遍历数组
25.      * @return 返回重建后的二叉树的根节点
26.      */
27.     public TreeNode buildTree(int[] inorder, int[] postorder) {
28.         // 如果中序遍历数组为空，返回 null
29.         if (inorder.length == 0) {
30.             return null;
31.         }
33.         // 获取根节点的值（后序遍历的最后一个元素）
34.         int rootValue = postorder[postorder.length - 1];
35.         TreeNode root = new TreeNode(rootValue);
37.         // 在中序遍历数组中找到根节点的位置
38.         int rootIndexInInorder = -1;
39.         for (int i = 0; i < inorder.length; i++) {
40.             if (inorder[i] == rootValue) {
41.                 rootIndexInInorder = i;
42.                 break;
43.             }
44.         }
46.         // 分割中序遍历数组为左子树和右子树部分
47.         int[] inLeft = Arrays.copyOfRange(inorder, 0, rootIndexInInorder);
48.         int[] inRight = Arrays.copyOfRange(inorder, rootIndexInInorder + 1, inorder.length);
50.         // 分割后序遍历数组为左子树和右子树部分
51.         int[] postLeft = Arrays.copyOfRange(postorder, 0, rootIndexInInorder);
52.         int[] postRight = Arrays.copyOfRange(postorder, rootIndexInInorder, postorder.length - 1);
54.         // 递归构建左子树和右子树
55.         root.left = buildTree(inLeft, postLeft);
56.         root.right = buildTree(inRight, postRight);
58.         // 返回重建后的根节点
59.         return root;
60.     }
61. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。