Leetcode刷题第五周

二叉树：
种类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
存储方式：链式存储、线式存储（顺序存储）
二叉数遍历：深度优先搜索（前序、中序、后序）：使用递归实现（实际用栈来实现）、迭代法（非递归的方式、栈），广度优先搜索（层序遍历）：用队列
递归三步走写法：1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑。
144、二叉树的前序遍历

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     // 方法一：递归法
22.     // public List<Integer> preorderTraversal(TreeNode root) {
23.     //     List<Integer> result = new ArrayList<>();
24.     //     preorder(root, result);
25.     //     return result;
26.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
27. 
28.     // public void preorder(TreeNode root, List<Integer> result){
29.     //     if(root == null){
30.     //         return;
31.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33.     //     result.add(root.val);
34.     //     preorder(root.left, result);
35.     //     preorder(root.right, result);
36.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 
38.     // 方法二：非递归的方法
39.     public List<Integer> preorderTraversal(TreeNode root) {
40.         List<Integer> result = new ArrayList<>();
41.         Stack<TreeNode> stack = new Stack<>();
42.         stack.push(root);
43.         while(!stack.isEmpty()){
44.             TreeNode cur = stack.pop();
45.             if(cur != null){
46.                 result.add(cur.val);
47.                 stack.push(cur.right);
48.                 stack.push(cur.left);
49.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
50. else{
51.                 continue;
52.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
53. 
54.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
55. 
56.         return result;
57.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
58. 
59. // 方法三：统一风格的非递归
60.     public List<Integer> preorderTraversal(TreeNode root) {
61.         List<Integer> result = new ArrayList<>();
62.         Stack<TreeNode> stack = new Stack<>();
63.         if(root != null){
64.             stack.push(root);
65.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
66. 
67.         while(!stack.isEmpty()){
68.             if(stack.peek() != null){
69.                 TreeNode cur = stack.pop();
70.                 if(cur.right != null){
71.                     stack.push(cur.right);
72.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
73. 
74.                 if(cur.left != null){
75.                     stack.push(cur.left);
76.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
77. 
78.                 stack.push(cur);
79.                 stack.push(null);
80.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
81. else{
82.                 stack.pop();
83.                 TreeNode cur = stack.pop();
84.                 result.add(cur.val);
85.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
86. 
87.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
88. 
89.         return result;
90.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
91. 
92. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
93. 

复制代码

145、二叉树的后序遍历

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     // 方法一：递归法
22.     // public List<Integer> postorderTraversal(TreeNode root) {
23.     //     List<Integer> result = new ArrayList<>();
24.     //     postOrder(root, result);
25.     //     return result;
26.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
27. 
28.     // public void postOrder(TreeNode root, List<Integer> result){
29.     //     if(root == null){
30.     //         return;
31.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33.     //     postOrder(root.left, result);
34.     //     postOrder(root.right, result);
35.     //     result.add(root.val);
36.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 
38.     // 方法二：非递归
39.     public List<Integer> postorderTraversal(TreeNode root) {
40.         List<Integer> result = new ArrayList<>();
41.         if(root == null){
42.             return result;
43.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
44. 
45.         Stack<TreeNode> stack = new Stack<>();
46.         stack.push(root);
47.         while(!stack.isEmpty()){
48.             TreeNode cur = stack.pop();
49.             result.add(cur.val);
50.             if(cur.left != null){
51.                 stack.push(cur.left);
52.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
53. 
54.             if(cur.right != null){
55.                 stack.push(cur.right);
56.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
57. 
58.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
59. 
60.         Collections.reverse(result);
61.         return result;
62.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
63. 
64. // 方法三：统一风格的非递归
65.     public List<Integer> postorderTraversal(TreeNode root) {
66.         List<Integer> result = new ArrayList<>();
67.         Stack<TreeNode> stack = new Stack<>();
68.         if(root != null){
69.             stack.push(root);
70.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
71. 
72.         while(!stack.isEmpty()){
73.             if(stack.peek() != null){
74.                 TreeNode cur = stack.pop();
75.                 stack.push(cur);
76.                 stack.push(null);
77.                 if(cur.right != null){
78.                     stack.push(cur.right);
79.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
80. 
81.                
82.                 if(cur.left != null){
83.                     stack.push(cur.left);
84.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
85. 
86.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
87. else{
88.                 stack.pop();
89.                 TreeNode cur = stack.pop();
90.                 result.add(cur.val);
91.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
92. 
93.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
94. 
95.         return result;
96.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
97. 
98. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
99. 

复制代码

94、二叉树的中序遍历

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     // 方法一：递归法
22.     // public List<Integer> inorderTraversal(TreeNode root) {
23.     //     List<Integer> result = new ArrayList<>();
24.     //     infixOrder(root, result);
25.     //     return result;
26.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
27. 
28.     // public void infixOrder(TreeNode root, List<Integer> result){
29.     //     if(root == null){
30.     //         return;
31.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33.     //     infixOrder(root.left, result);
34.     //     result.add(root.val);
35.     //     infixOrder(root.right, result);
36.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 
38.     // 方法二：非递归
39.     public List<Integer> inorderTraversal(TreeNode root) {
40.         List<Integer> result = new ArrayList<>();
41.         if(root == null){
42.             return result;
43.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
44. 
45.         Stack<TreeNode> stack = new Stack<>();
46.         TreeNode cur = root;
47.         while(cur != null || !stack.isEmpty()){
48.             if(cur != null){
49.                 stack.push(cur);
50.                 cur = cur.left;
51.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
52. else{
53.                 cur = stack.pop();
54.                 result.add(cur.val);
55.                 cur = cur.right;
56.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
57. 
58.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
59. 
60.         return result;
61.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
62. 
63. // 方法三：统一风格的非递归
64.     public List<Integer> inorderTraversal(TreeNode root) {
65.         List<Integer> result = new ArrayList<>();
66.         Stack<TreeNode> stack = new Stack<>();
67.         if(root != null){
68.             stack.push(root);
69.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
70. 
71.         while(!stack.isEmpty()){
72.             if(stack.peek() != null){
73.                 TreeNode cur = stack.pop();
74.                 if(cur.right != null){
75.                     stack.push(cur.right);
76.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
77. 
78.                 stack.push(cur);
79.                 stack.push(null);
80.                 if(cur.left != null){
81.                     stack.push(cur.left);
82.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
83. 
84.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
85. else{
86.                 stack.pop();
87.                 TreeNode cur = stack.pop();
88.                 result.add(cur.val);
89.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
90. 
91.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
92. 
93.         return result;
94.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
95. 
96. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
97. 

复制代码

广度优先搜索：层序遍历
102、二叉树的层序遍历

1. class Solution {
2.     public List<List<Integer>> levelOrder(TreeNode root) {
3.         List<List<Integer>> list = new ArrayList<List<Integer>>();
4.         Queue<TreeNode> queue = new LinkedList<>();
5.         int size = 0;
6.         if(root != null){
7.             queue.offer(root);
8.             size = 1;
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         while(!queue.isEmpty()){
12.             List<Integer> list1 = new ArrayList<>();
13.             while(size > 0){
14.                 TreeNode cur = queue.poll();
15.                 list1.add(cur.val);
16.                 if(cur.left != null){
17.                     queue.offer(cur.left);
18.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.                 if(cur.right != null){
21.                     queue.offer(cur.right);
22.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.                 size--;
25.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.             size = queue.size();
28.             list.add(list1);
29.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31.         return list;
32.         
34.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
35. 
36. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 

复制代码

107、二叉树的层序遍历 II

1. class Solution {
2.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
3.         List<List<Integer>> list = new ArrayList<>();
4.         Queue<TreeNode> queue = new LinkedList<>();
5.         int size = queue.size();
6.         if(root != null){
7.             queue.offer(root);
8.             size = queue.size();
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         while(!queue.isEmpty()){
12.             List<Integer> list1 = new ArrayList<>();
13.             while(size > 0){
14.                 TreeNode cur = queue.poll();
15.                 list1.add(cur.val);
16.                 if(cur.left != null){
17.                     queue.offer(cur.left);
18.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.                 if(cur.right != null){
21.                     queue.offer(cur.right);
22.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.                 size--;
25.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.             size = queue.size();
28.             list.add(list1);
29.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31.         Collections.reverse(list);
32.         return list;
33.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 

复制代码

199、二叉树的右视图

1. class Solution {
2.     public List<Integer> rightSideView(TreeNode root) {
3.         List<Integer> resultList = new ArrayList<>();
4.         Deque<TreeNode> deque = new LinkedList<>();
5.         int size = deque.size();
6.         if(root != null){
7.             deque.offer(root);
8.             size = deque.size();
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         while(!deque.isEmpty()){
12.             TreeNode cur = deque.peekLast();
13.             resultList.add(cur.val);
14.             while(size > 0){
15.                 cur = deque.poll();
16.                 if(cur.left != null){
17.                     deque.offer(cur.left);
18.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.                 if(cur.right != null){
21.                     deque.offer(cur.right);
22.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.                 size--;
25.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.             size = deque.size();
28.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
29. 
30.         return resultList;
31.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 

复制代码

637、二叉树的层平均值

1. class Solution {
2.     public List<Double> averageOfLevels(TreeNode root) {
3.         List<Double> resultList =  new ArrayList<>();
4.         Queue<TreeNode> queue = new LinkedList<>();
5.         int size = queue.size();
6.         Double sum = 0.0;
7.         int count = 0;
8.         if(root != null){
9.             queue.offer(root);
10.             size = queue.size();
11.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
12. 
13.         while(!queue.isEmpty()){
14.             count = size;
15.             while(size > 0){
16.                 TreeNode cur = queue.poll();
17.                 sum += cur.val;
18.                 if(cur.left != null){
19.                     queue.offer(cur.left);
20.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
21. 
22.                 if(cur.right != null){
23.                     queue.offer(cur.right);
24.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
25. 
26.                 size--;
27.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
28. 
29.             resultList.add(sum/count);
30.             sum = 0.0;
31.             size = queue.size();
32.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
33. 
34.         return resultList;
35.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 
37. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
38. 

复制代码

429、N 叉树的层序遍历

1. class Solution {
2.     public List<List<Integer>> levelOrder(Node root) {
3.         List<List<Integer>> resultList = new ArrayList<>();
4.         Queue<Node> queue = new LinkedList<>();
5.         int size = queue.size();
6.         if(root != null){
7.             queue.offer(root);
8.             size = queue.size();
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         while(!queue.isEmpty()){
12.             List<Integer> list = new ArrayList<>();
13.             while(size > 0){
14.                 Node cur = queue.poll();
15.                 list.add(cur.val);
16.                 for(Node node: cur.children){
17.                     if(node != null){
18.                         queue.offer(node);
19.                     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
20. 
21.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
22. 
23.                 size--;
24.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
25. 
26.             resultList.add(list);
27.             size = queue.size();
28.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
29. 
30.         return resultList;
31.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 

复制代码

515、在每个树行中找最大值

1. class Solution {
2.     public List<Integer> largestValues(TreeNode root) {
3.         List<Integer> resultList = new ArrayList<>();
4.         Queue<TreeNode> queue = new LinkedList<>();
5.         int size = queue.size();
6.         if(root != null){
7.             queue.offer(root);
8.             size = queue.size();
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         int max = Integer.MIN_VALUE;
12.         while(!queue.isEmpty()){
13.             while(size > 0){
14.                 TreeNode cur = queue.poll();
15.                 max = max > cur.val ? max : cur.val;
16.                 if(cur.left != null){
17.                     queue.offer(cur.left);
18.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.                 if(cur.right != null){
21.                     queue.offer(cur.right);
22.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.                 size--;
25.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.             resultList.add(max);
28.             max = Integer.MIN_VALUE;
29.             size = queue.size();
30.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
31. 
32.         return resultList;
33.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 
35. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 

复制代码

116

1. class Solution {
2.     public Node connect(Node root) {
3.         Queue<Node> queue = new LinkedList<>();
4.         int size = 0;
5.         if(root != null){
6.             queue.offer(root);
7.             size = queue.size();
8.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
9. 
10.         while(!queue.isEmpty()){
11.             while(size > 0){
12.                 Node temp = queue.poll();
13.                 if(size > 1){
14.                     temp.next = queue.peek();
15.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17.                 if(temp.left != null){
18.                     queue.offer(temp.left);
19.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
20. 
21.                 if(temp.right != null){
22.                     queue.offer(temp.right);
23.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
24. 
25.                 size--;
26.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
27. 
28.             size = queue.size();
29.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31.         return root;
32.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
33. 
34. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
35. 

复制代码

117、填充每个节点的下一个右侧节点指针 II

同上！
104、二叉树的最大深度
![]
(https://img2022.cnblogs.com/blog/3018498/202211/3018498-20221121204402960-1570599807.png)

1. class Solution {
2.     public int maxDepth(TreeNode root) {
3.         return count(root, 0);
5.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
6. 
7.     public int count(TreeNode root, int depth){
8.         if(root == null){
9.             return depth;
10.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
11. 
12.         depth++;
13.         return Math.max(count(root.left, depth),count(root.right, depth));
14.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
15. 
16. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
17. 

复制代码

111、二叉树的最小深度

1. class Solution {
2.     public int minDepth(TreeNode root) {
3.         Queue<TreeNode> queue = new LinkedList<>();
4.         int size = queue.size();
5.         int depth = 0;
6.         if(root != null){
7.             queue.offer(root);
8.             size = queue.size();
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         while(!queue.isEmpty()){
12.             depth++;
13.             while(size > 0){
14.                 TreeNode cur = queue.poll();
15.                 if(cur.left == null && cur.right == null){
16.                     return depth;
17.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19.                 if(cur.left != null){
20.                     queue.offer(cur.left);
21.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
22. 
23.                 if(cur.right != null){
24.                     queue.offer(cur.right);
25.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.                 size--;
28.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
29. 
30.             size = queue.size();
31.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 
33.         return depth;
34.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
35. 
36. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 

复制代码

226、翻转二叉树

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     // 方法一：层次遍历，广度优先算法
22.     // public TreeNode invertTree(TreeNode root) {
23.     //     Queue<TreeNode> queue = new LinkedList<>();
24.     //     int size = queue.size();
25.     //     if(root != null){
26.     //         queue.offer(root);
27.     //         size = queue.size();
28.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
29. 
30.     //     while(!queue.isEmpty()){
31.     //         while(size > 0){
32.     //             TreeNode cur = queue.poll();
33.     //             if(cur.left != null){
34.     //                 queue.offer(cur.left);
35.     //             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 
37.     //             if(cur.right != null){
38.     //                 queue.offer(cur.right);
39.     //             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
40. 
41.     //             swapChildren(cur);
42.     //             size--;
43.     //         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
44. 
45.     //         size = queue.size();
46.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
47. 
48.     //     return root;
49.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
50. 
51.     // public void swapChildren(TreeNode cur){
52.     //     TreeNode temp = cur.left;
53.     //     cur.left = cur.right;
54.     //     cur.right = temp;
55.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
56. 
57.     // 方法二：递归法，中序
58.     // public TreeNode invertTree(TreeNode root) {
59.     //     if(root == null){
60.     //         return root;
61.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
62. 
63.     //     invertTree(root.left);
64.     //     invertTree(root.right);
65.     //     swapChildren(root);
66.     //     return root;
67.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
68.      
69.     // public void swapChildren(TreeNode cur){
70.     //     TreeNode temp = cur.left;
71.     //     cur.left = cur.right;
72.     //     cur.right = temp;
73.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
74. 
75.     // 方法三：迭代法：中序，统一风格
76.     public TreeNode invertTree(TreeNode root) {
77.         Stack<TreeNode> stack = new Stack<>();
78.         if(root != null){
79.             stack.push(root);
80.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
81. 
82.         while(!stack.isEmpty()){
83.             if(stack.peek() != null){
84.                 TreeNode cur = stack.pop();
85.                 if(cur.right != null)
86.                 stack.push(cur.right);
87.                 if(cur.left != null)
88.                 stack.push(cur.left);
89.                 stack.push(cur);
90.                 stack.push(null);
91.                 swapChildren(cur);
92.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
93. else{
94.                 stack.pop();
95.                 stack.pop();
96.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
97. 
98.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
99. 
100.         return root;
101.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
102.      
103.     public void swapChildren(TreeNode cur){
104.         TreeNode temp = cur.left;
105.         cur.left = cur.right;
106.         cur.right = temp;
107.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
108. 
109. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
110. 

复制代码

589、N 叉树的前序遍历

1. class Solution {
2.     // 方法一：递归
3.     // public List<Integer> resultList = new ArrayList<>();
4.     // public List<Integer> preorder(Node root) {
5.     //     if(root == null){
6.     //         return resultList;
7.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9.     //     resultList.add(root.val);
10.     //     for(Node node : root.children){
11.     //         preorder(node);
12.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
13. 
14.     //     return resultList;
15.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17.     // 方法二：迭代，统一风格
18.     public List<Integer> preorder(Node root) {
19.         List<Integer> resultList = new ArrayList<>();
20.         Stack<Node> stack = new Stack<>();
21.         if(root != null){
22.             stack.push(root);
23.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
24. 
25.         while(!stack.isEmpty()){
26.             if(stack.peek() != null){
27.                 Node cur = stack.pop();
28.                 List<Node> list = new ArrayList<>();
29.                 list = cur.children;
30.                 for(int i = list.size() - 1; i >= 0; i--){
31.                     if(list.get(i) != null){
32.                         stack.push(list.get(i));
33.                     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 
35.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 
37.                 stack.push(cur);
38.                 stack.push(null);
39.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
40. else{
41.                 stack.pop();
42.                 Node cur = stack.pop();
43.                 resultList.add(cur.val);
44.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
45. 
46.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
47. 
48.         return resultList;
49.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
50. 
51. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
52. 

复制代码

590、N 叉树的后序遍历
101、对称二叉树

1. class Solution {
2.     // 方法一：递归，后序遍历
3.     // public boolean isSymmetric(TreeNode root) {
4.     //     return compare(root.left, root.right);
5.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
6. 
7.     // public boolean compare(TreeNode left, TreeNode right){
8.     //     if(left == null && right != null){
9.     //         return false;
10.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
11. 
12.     //     if(right == null && left != null){
13.     //         return false;
14.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
15. 
16.     //     if(right == null && left == null){
17.     //         return true;
18.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.     //     if(left.val != right.val){
21.     //         return false;
22.     //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.     //     boolean resultLeft = compare(left.left, right.right);
25.     //     boolean resultRight = compare(left.right, right.left);
26.     //     return resultLeft && resultRight;
27.     // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
28. 
29.     // 方法二：迭代
30.     public boolean isSymmetric(TreeNode root) {
31.         Deque<TreeNode> deque = new LinkedList<>();
32.         deque.offerFirst(root.left);
33.         deque.offerLast(root.right);
34.         while(!deque.isEmpty()){
35.             TreeNode left = deque.pollFirst();
36.             TreeNode right = deque.pollLast();
37.             if(left == null && right == null){
38.                 continue;
39.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
40. 
41.             if(left == null && right != null){
42.                 return false;
43.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
44. 
45.             if(left != null && right == null){
46.                 return false;
47.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
48. 
49.             if(left.val != right.val){
50.                 return false;
51.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
52. 
53.             deque.offerFirst(left.left);
54.             deque.offerFirst(left.right);
55.             deque.offerLast(right.right);
56.             deque.offerLast(right.left);
57.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
58. 
59.         return true;
60.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
61. 
62. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
63. 

复制代码

559、N 叉树的最大深度

1. class Solution {
2.     public int maxDepth(Node root) {
3.         return preOrder(root);
4.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
5. 
6.     public int preOrder(Node root){
7.         if(root == null){
8.             return 0;
9.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.         int depth = 0;
12.         for(Node node : root.children){
13.             depth = Math.max(depth, preOrder(node));
14.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
15. 
16.         return depth + 1;
17.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
20. 

复制代码

对称二叉树
二叉树的最大深度
二叉树的最小深度
完全二叉树的节点个数
平衡二叉树
二叉树的所有路径
404、左叶子之和

1.     public int sumOfLeftLeaves(TreeNode root) {
2.         if(root == null){
3.             return 0;
4.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
5. 
6.         int left = sumOfLeftLeaves(root.left);
7.         int right = sumOfLeftLeaves(root.right);
8.         int val = 0;
9.         if(root.left != null && root.left.left == null &&root.left.right == null){
10.             val = root.left.val;
11.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
12. 
13.         int sum = left + right + val;
14.         return sum;
15.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 

复制代码

513找树左下角的值

1. class Solution {
2.     public int findBottomLeftValue(TreeNode root) {
3.         Queue<TreeNode> queue = new LinkedList<>();
4.         int size  = queue.size();
5.         if(root != null){
6.             queue.offer(root);
7.             size = queue.size();
8.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
9. 
10.         int find = 0;
11.         while(!queue.isEmpty()){
12.             Queue<TreeNode> result = new LinkedList<>();
13.             while(size > 0){
14.                 TreeNode cur = queue.poll();
15.                 result.offer(cur);
16.                 if(cur.left != null){
17.                     queue.offer(cur.left);
18.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.                 if(cur.right != null){
21.                     queue.offer(cur.right);
22.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.                 size--;
25.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.             size = queue.size();
28.             find = result.peek().val;
29.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31.         return find;
33.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. 
35. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 

复制代码

112、路径总和

1. class Solution {
2.     public boolean hasPathSum(TreeNode root, int targetSum) {
3.         if(root == null){
4.             return false;
5.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
6. 
7.         List<Integer> result = new ArrayList<>();
8.         List<Integer> temp = new ArrayList<>();
9.         pathSum(root, result, temp);
10.         return result.contains(targetSum);
11.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
12. 
13.     public void pathSum(TreeNode root, List<Integer> result, List<Integer> temp){
14.         temp.add(root.val);
15.         if(root.left == null && root.right == null){
16.             int sum = 0;
17.             for(int i = 0; i < temp.size(); i++){
18.                 sum += temp.get(i);
19.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
20. 
21.             result.add(sum);
22.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
23. 
24.         if(root.left != null){
25.             pathSum(root.left, result, temp);
26.             temp.remove(temp.size() - 1);
27.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
28. 
29.         if(root.right != null){
30.             pathSum(root.right, result, temp);
31.             temp.remove(temp.size() - 1);
32.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
33. 
34.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
35. 
36. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 

复制代码

113、路径总和 II

1. class Solution {
2.     public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
3.         List<List<Integer>> result = new ArrayList<>();
4.         List<Integer> temp = new ArrayList<>();
5.         if(root == null){
6.             return result;
7.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9.         find(root, result, temp, targetSum);
10.         return result;
11.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
12. 
13.     public void find(TreeNode root, List<List<Integer>> result, List<Integer> temp, int targetSum){
14.         temp.add(root.val);
15.         if(root.left == null && root.right == null){
16.             int sum = 0;
17.             for(int i = 0; i < temp.size(); i++){
18.                 sum += temp.get(i);
19.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
20. 
21.             if(sum == targetSum){
22.                 result.add(new ArrayList<Integer>(temp));
23.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
24. 
25.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.         if(root.left != null){
28.             find(root.left, result, temp, targetSum);
29.             temp.remove(temp.size() - 1);
30.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
31. 
32.         if(root.right != null){
33.             find(root.right, result, temp, targetSum);
34.             temp.remove(temp.size() - 1);
35.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
36. 
37.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
38. 
39. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
40. 

复制代码

106、从中序与后序遍历序列构造二叉树

1. class Solution {
2.     public Map<Integer, Integer> map;
3.     public TreeNode buildTree(int[] inorder, int[] postorder) {
4.         map = new HashMap<>();
5.         for(int i = 0; i < inorder.length; i++){
6.             map.put(inorder[i], i);
7.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9.         return find(inorder, 0, inorder.length, postorder, 0, postorder.length);
10.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
11. 
12.     public TreeNode find(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend){
13.         if(inbegin >= inend || pobegin >= poend){
14.             return null;
15.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17.         int temp = map.get(postorder[poend - 1]);
18.         int len = temp - inbegin;
19.         TreeNode root = new TreeNode(inorder[temp]);
20.         root.left = find(inorder, inbegin, temp, postorder, pobegin, pobegin + len);
21.         root.right = find(inorder, temp + 1, inend, postorder, pobegin + len, poend - 1);
22.         return root;
23.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
24. 
25. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 

复制代码

105、从前序与中序遍历序列构造二叉树

1. class Solution {
2.     public Map<Integer, Integer> map;
3.     public TreeNode buildTree(int[] preorder, int[] inorder) {
4.         map = new HashMap<>();
5.         for(int i = 0; i < inorder.length; i++){
6.             map.put(inorder[i], i);
7.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9.         return find(inorder, 0, inorder.length, preorder, 0, preorder.length);
10.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
11. 
12.     public TreeNode find(int[] inorder, int inbegin, int inend, int[] preorder, int prbegin, int prend){
13.         if(inbegin >= inend || prbegin >= prend){
14.             return null;
15.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17.         int temp = map.get(preorder[prbegin]);
18.         int len = temp - inbegin;
19.         TreeNode root = new TreeNode(inorder[temp]);
20.         root.left = find(inorder, inbegin, temp, preorder, prbegin + 1, prbegin + len + 1);
21.         root.right = find(inorder, temp + 1, inend, preorder, prbegin + len + 1, prend);
22.         return root;
23.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
24. 
25. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 

复制代码

654、最大二叉树

1. class Solution {
2.     public Map<Integer, Integer> map;
3.     public TreeNode constructMaximumBinaryTree(int[] nums) {
4.         map = new HashMap<>();
5.         for(int i = 0; i < nums.length; i++){
6.             map.put(nums[i], i);
7.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9.         return binaryTree(nums, 0, nums.length - 1);
10.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
11. 
12.     public TreeNode binaryTree(int[] nums, int left, int right){
13.         int max = -1;
14.         for(int i = left; i <= right; i++){
15.             max = max > nums[i] ? max : nums[i];
16.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
17. 
18.         if(max == -1){
19.             return null;
20.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
21. else{
22.             int index = map.get(max);
23.             TreeNode root = new TreeNode(max);
24.             root.left = binaryTree(nums, left, index - 1);
25.             root.right = binaryTree(nums, index + 1, right);
26.             return root;
27.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
28. 
29.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
32. 

复制代码

617、合并二叉树

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     public TreeNode result = new TreeNode();
22.     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
23.         // 前序遍历，递归
24.         // if(root1 == null){
25.         //     return root2;
26.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
27. 
28.         // if(root2 == null){
29.         //     return root1;
30.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
31. 
32.         // root1.val += root2.val;
33.         // root1.left = mergeTrees(root1.left,root2.left);
34.         // root1.right = mergeTrees(root1.right,root2.right);
35.         // return root1;
36.         // 使用栈迭代
37.         // if(root1 == null){
38.         //     return root2;
39.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
40. 
41.         // if(root2 == null){
42.         //     return root1;
43.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
44. 
45.         // Stack<TreeNode> stack = new Stack<>();
46.         // stack.push(root1);
47.         // stack.push(root2);
48.         // while(!stack.isEmpty()){
49.         //     TreeNode cur2 = stack.pop();
50.         //     TreeNode cur1 = stack.pop();
51.         //     cur1.val += cur2.val;
52.         //     if(cur1.left != null && cur2.left != null){
53.         //         stack.push(cur1.left);
54.         //         stack.push(cur2.left);
55.         //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
56. else{
57.         //         if(cur1.left == null){
58.         //             cur1.left = cur2.left;
59.         //         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
60. 
61.         //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
62. 
63.         //     if(cur1.right != null && cur2.right != null){
64.         //         stack.push(cur1.right);
65.         //         stack.push(cur2.right);
66.         //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
67. else{
68.         //         if(cur1.right == null){
69.         //             cur1.right = cur2.right;
70.         //         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
71. 
72.         //     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
73. 
74.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
75. 
76.         // return root1;
77.         // 使用队列迭代
78.         if(root1 == null){
79.             return root2;
80.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
81. 
82.         if(root2 == null){
83.             return root1;
84.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
85. 
86.         Queue<TreeNode> queue = new LinkedList<>();
87.         queue.offer(root1);
88.         queue.offer(root2);
89.         while(!queue.isEmpty()){
90.             TreeNode cur1 = queue.poll();
91.             TreeNode cur2 = queue.poll();
92.             cur1.val += cur2.val;
93.             if(cur1.left != null && cur2.left != null){
94.                 queue.offer(cur1.left);
95.                 queue.offer(cur2.left);
96.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
97. else{
98.                 if(cur1.left == null){
99.                     cur1.left = cur2.left;
100.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
101. 
102.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
103. 
104.             if(cur1.right != null && cur2.right != null){
105.                 queue.offer(cur1.right);
106.                 queue.offer(cur2.right);
107.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
108. else{
109.                 if(cur1.right == null){
110.                     cur1.right = cur2.right;
111.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
112. 
113.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
114. 
115.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
116. 
117.         return root1;
118.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
119. 
120. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
121. 

复制代码

700、二叉搜索树中的搜索

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
8. 
9. *     TreeNode(int val) { this.val = val; [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11. *     TreeNode(int val, TreeNode left, TreeNode right) {
12. *         this.val = val;
13. *         this.left = left;
14. *         this.right = right;
15. *     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
16. 
17. * [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
18. 
19. */
20. class Solution {
21.     public TreeNode searchBST(TreeNode root, int val) {
22.         // 递归
23.         // if(root == null){
24.         //     return null;
25.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
26. 
27.         // TreeNode result = new TreeNode();
28.         // if(root.val == val){
29.         //     result = root;
30.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
31. else if(root.val < val){
32.         //     result = searchBST(root.right,val);
33.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
34. else{
35.         //     result = searchBST(root.left,val);
36.         // [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
37. 
38.         // return result;
39.         // 迭代
40.         Stack<TreeNode> stack = new Stack<>();
41.         stack.push(root);
42.         while(!stack.isEmpty()){
43.             TreeNode cur = stack.pop();
44.             if(cur.val == val){
45.                 return cur;
46.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
47. else if(cur.val < val){
48.                 if(cur.right == null){
49.                     return null;
50.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
51. 
52.                 stack.push(cur.right);
53.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
54. else{
55.                 if(cur.left == null){
56.                     return null;
57.                 [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
58. 
59.                 stack.push(cur.left);
60.             [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
61. 
62.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
63. 
64.         return null;
65.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
66. 
67. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
68. 

复制代码

98、验证二叉搜索树

1. class Solution {
2.     public boolean isValidBST(TreeNode root) {
3. // 需要从底层往上传递判断结果，所以采用后序遍历
4.         if(root == null){
5.             return true;
6.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
7. 
8.         return isValidBST1(root,Long.MIN_VALUE,Long.MAX_VALUE);
9.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
10. 
11.     public boolean isValidBST1(TreeNode root,long left, long right){
12.         if(root == null){
13.             return true;
14.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
15. 
16.         if(root != null && (root.val <= left || root.val >= right)){
17.             return false;
18.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
19. 
20.         boolean leftFlag = isValidBST1(root.left,left,root.val);
21.         boolean rightFlag = isValidBST1(root.right,root.val,right);
22.         if(leftFlag == false || rightFlag == false){
23.             return false;
24.         [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
25. 
26.         return leftFlag && rightFlag;
27.     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
28. 
29. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
30. 
31. [530](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/)、二叉搜索树的最小绝对差
32. 

复制代码

class Solution {
public int result = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return result;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
traversal(root);
return result;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
public void traversal(TreeNode cur){
if(cur == null){
return;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
traversal(cur.left);
if(pre != null){
result = Math.min(result, cur.val - pre.val);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
pre = cur;
traversal(cur.right);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [501](https://leetcode.cn/problems/find-mode-in-binary-search-tree/)、二叉搜索树中的众数
2. 

复制代码

class Solution {
public int Maxcount;
public int count;
public List result;
public TreeNode pre;
public int[] findMode(TreeNode root) {
Maxcount = 0;
count = 0;
result = new ArrayList();
pre = null;
traversal(root);
int[] find = new int[result.size()];
for(int i = 0; i < result.size(); i++){
find = result.get(i);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
return find;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
public void traversal(TreeNode root){
if(root == null){
return;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
traversal(root.left);
if(pre == null || root.val != pre.val){
count = 1;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
else{
count++;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
pre = root;
if(count > Maxcount){
result.clear();
result.add(root.val);
Maxcount = count;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
else if(count == Maxcount){
result.add(root.val);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
traversal(root.right);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [236](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)、二叉树的最近公共祖先
2. 

复制代码

class Solution {
public TreeNode result = null;
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//     // 1、后序遍历，从下往上传递，从遇到p或q开始，往上传递true,当某个节点也叶子节点都为true时，找到最近工祖先
//     // 递归
//     postOrder(root,p.val,q.val);
//     return result;
// [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
// public boolean postOrder(TreeNode root, int p, int q){
//     if(root == null){
//         return false;
//     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
//     boolean leftFlag = postOrder(root.left,p,q);
//     boolean rightFlag = postOrder(root.right,p,q);
//     if(leftFlag && rightFlag){
//         result = root;
//         return true;
//     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
//     if((root.val == q || root.val == p) && (leftFlag || rightFlag)){
//         result = root;
//         return true;
//     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
//     if(root.val == q || root.val == p){
//         return true;
//     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
//     if(leftFlag || rightFlag){
//         return true;
//     [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
//     return false;
// [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [235](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/)、二叉搜索树的最近公共祖先
2. 

复制代码

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int left = Math.min(p.val,q.val);
int right = Math.max(p.val,q.val);
return infixTravesal(root,left,right);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
public TreeNode infixTravesal(TreeNode root,int left,int right){
if(root == null){
return root;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
if(root.val >= left && root.val  val && root.left == null){
root.left = new TreeNode(val);
return;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
else{
travesal(root.left,val);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [701](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)、二叉搜索树中的插入操作
2. 

复制代码

class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = delete(root,key);
return root;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
public TreeNode delete(TreeNode root,int key){
if(root == null){
return null;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
if(root.val < key){
root.right = delete(root.right,key);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
else if(root.val > key){
root.left = delete(root.left,key);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
else{
if(root.left == null)
return root.right;
if(root.right == null)
return root.left;
TreeNode cur = root.right;
TreeNode temp = root.right;
while(temp.left != null){
temp = temp.left;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
temp.left = root.left;
return cur;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
return root;

1. [450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
2. 

复制代码

[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. }

复制代码

class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null){
return null;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
if(root.val < low){
return trimBST(root.right,low,high);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
if(root.val > high){
return trimBST(root.left,low,high);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [669](https://leetcode.cn/problems/trim-a-binary-search-tree/)、修剪二叉搜索树
2. 

复制代码

class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return travesal(nums,0,nums.length - 1);
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
public TreeNode travesal(int[] nums, int left, int right){
if(left > right){
return null;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
int mid = left + (right - left)/2;
TreeNode result = new TreeNode(nums[mid]);
result.left = travesal(nums,left,mid - 1);
result.right = travesal(nums,mid + 1, right);
return result;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点

1. [108](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)、将有序数组转换为二叉搜索树
2. 

复制代码

class Solution {
public int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);

1.     return root;[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
2. 

复制代码

[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、删除二叉搜索树中的节点
[code][/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！