力扣labuladong——一刷day44

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维。 代码看起来虽然多，但思路非常简单：用 path 维护递归遍历的路径，到达叶子节点的时候判断字典序最小的路径。 不要忘了在叶子节点的时候也要正确维护 path 变量，而且要把 StringBuilder 中的字符串反转才是目想要的答案。

一、力扣298. 二叉树最长连续序列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 1;
    public int longestConsecutive(TreeNode root) {
        fun(root, 1, Integer.MIN_VALUE);
        return res;
    }
    public void fun(TreeNode root, int len, int parentVal){
        if(root == null){
            return ;
        }
        if(root.val == parentVal+1){
            len ++;
        }else{
            len = 1;
        }
        res = Math.max(len, res);
        fun(root.left, len, root.val);
        fun(root.right,len,root.val);
    }
}
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

二、力扣988. 从叶结点开始的最小字符串

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    String res = null;
    StringBuilder sb = new StringBuilder();
    public String smallestFromLeaf(TreeNode root) {
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        sb.append((char)('a'+root.val));
        if(root.left == null && root.right == null){
            sb.reverse();
            String s = sb.toString();
            if(res == null || res.compareTo(s) > 0){
                res = s;
            }
            sb.reverse();
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        fun(root.left);
        fun(root.right);
        sb.deleteCharAt(sb.length()-1);
    }
}
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

三、力扣1022. 从根到叶的二进制数之和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    int path = 0;
    public int sumRootToLeaf(TreeNode root) {
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        path = path << 1 | root.val;
        if(root.left == null && root.right == null){
            res += path;

        }
        fun(root.left);
        fun(root.right);
        path = path >> 1;
    }
}
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

四、力扣1457. 二叉树中的伪回文路径

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> path = new ArrayList<>();
    int[] arr = new int[10];
    int count = 0;
    public int pseudoPalindromicPaths (TreeNode root) {
        fun(root);
        return count;
    }
    public void fun(TreeNode root){
        if(root == null){
            return ;
        }
        path.add(root.val);
        arr[root.val] ++;
        if(root.left == null && root.right == null){
            int flag = 0;
            for(int i = 0; i < 10; i ++){
                if(arr[i]%2 == 1){
                    flag ++;
                }
            }
            if(flag <= 1){
                count ++;
            }
            arr[root.val] --;
            return;
        }
        fun(root.left);
        fun(root.right);
        path.remove(path.size()-1);
        arr[root.val] --;
    }
}
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

五、力扣