LeetCode算法练习top100：（5）二叉树

package top100.top二叉树;

import top100.TreeNode;

import java.util.*;

public class TOP {
    //94. 二叉树的中序遍历
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return res;
    }
    private void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            res.add(root.val);
            inorder(root.right);
        }
    }


    //104. 二叉树的最大深度
    int maxDepth = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return maxDepth;
        }
        dfsMaxDepth(root, 0);
        return maxDepth;
    }
    private void dfsMaxDepth(TreeNode root, int res) {
        if (root == null) {
            maxDepth = Math.max(maxDepth, res);
        } else {
            dfsMaxDepth(root.left, res + 1);
            dfsMaxDepth(root.right, res + 1);
        }
    }


    //226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    //101. 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        } else {
            return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
        }
    }


    //543. 二叉树的直径
    int diameterOfBinaryTree = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfsDiameterOfBinaryTree(root);
        return diameterOfBinaryTree;
    }
    //计算当前节点到其叶子节点的最长距离
    private int dfsDiameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        //左右节点的最长距离
        int l = dfsDiameterOfBinaryTree(root.left);
        int r = dfsDiameterOfBinaryTree(root.right);
        diameterOfBinaryTree = Math.max(diameterOfBinaryTree, l + r);
        return Math.max(l, r) + 1;
    }


    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }


    //108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        int start = 0, mid = (nums.length - 1) / 2;
        TreeNode root = new TreeNode(nums[mid]); //二叉搜索树的根节点是中序遍历数组中间的数
        if (mid - start > 0) { //如果数组可以构成左子树
            root.left = sortedArrayToBST(Arrays.copyOfRange(nums, start, mid));
        }
        if (mid < nums.length - 1) { //如果数组可以构成右子树
            root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid + 1, nums.length));
        }
        return root;
    }


    //98. 验证二叉搜索树
    long preVal = Long.MIN_VALUE; //为了通过测试用例，设置比int最小还要小的值
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        //先判断左子树是否满足
        if (!isValidBST(root.left)) {
            return false;
        }
        //中序是否满足递增
        if (root.val <= preVal) {
            return false;
        }
        preVal = root.val; //更新pre值
        //判断又子树
        return isValidBST(root.right);
    }


    //230. 二叉搜索树中第K小的元素
    int res1;
    int k;
    ArrayList<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inOrder(root, k);
        return res1;
    }
    //中序遍历,从最小结点开始遍历:二叉搜索树的中序遍历为递增序列
    private void inOrder(TreeNode root, int k) {
        if (root == null) return;
        if (root.left != null) {
            inOrder(root.left, k);
        }
        list.add(root.val);
        if (list.size() == k) {
            res1 = root.val;
            return;
        }
        if (root.right != null) {
            inOrder(root.right, k);
        }
    }
    //230. 二叉搜索树中第K小的元素
    int res1;
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inOrder(root);
        return res1;
    }
    private void inOrder(TreeNode root) {
        if (root == null) return;
        //先递归到左端点
        inOrder(root.left);
        if (k == 0) return;
        //遍历到第k个
        if (--k == 0) res1 = root.val;
        //中序遍历
        inOrder(root.right);
    }


    //199. 二叉树的右视图
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                if (i == n - 1) {
                    res.add(cur.val);
                }
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
        }
        return res;
    }


    //114. 二叉树展开为链表
    //方法1：逆前序遍历
    TreeNode preTreeNode = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = preTreeNode;
        preTreeNode = root;
    }
    //方法2：前序遍历后重组
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        preOder(root, list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode pre = list.get(i - 1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
    private void preOder(TreeNode root, ArrayList<TreeNode> list) {
        if (root != null) {
            list.add(root);
            if (root.left != null) {
                preOder(root.left, list);
            }
            if (root.right != null) {
                preOder(root.right, list);
            }
        }
    }


    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        //获取根节点在中序的位置
        int mid = 0;
        for (int i = 0; i < n; i++) {
            if (inorder[i] == preorder[0]) {
                mid = i;
                break;
            }
        }
        //构造左右子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, mid + 1), Arrays.copyOfRange(inorder, 0, mid));
        root.right = buildTree(Arrays.copyOfRange(preorder, mid + 1, preorder.length), Arrays.copyOfRange(inorder, mid + 1, inorder.length));
        return root;
    }


    //437. 路径总和 III
    int res4 = 0;
    //从每个节点dfs
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        //遍历每个节点 bfs
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                dfs4(cur, targetSum);
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
        }
        return res4;
    }
    private void dfs4(TreeNode root, long curSum) {
        if (root != null) {
            curSum -= root.val;
            if (curSum == 0) {
                res4++;
            }
            //递归
            dfs4(root.left, curSum);
            dfs4(root.right, curSum);
        }
    }


    //236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }


    //124. 二叉树中的最大路径和
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs6(root);
        return res;
    }
    //计算root作为父结点所在在路径的最大路径和
    private int dfs6(TreeNode root) {
        if (root == null) return 0;
        //计算左子树的最大路径和,抛弃负数的路径
        int left = Math.max(0, dfs6(root.left));
        int right = Math.max(0, dfs6(root.right));
        //计算路径 left -> root -> right 的和
        res = Math.max(res, left + right + root.val);
        //返回root结点所在的子树最大路径和给父结点使用
        return root.val + Math.max(left, right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342