2025-4月算法刷题

发表于 | 分类于

屏幕截图 2025-04-20 232915

对称二叉树

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
/**
 * 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 {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isMirror(root.left,root.right);
    }

    private boolean isMirror(TreeNode left,TreeNode right){
        if(left == null&&right==null){
            return true;
        }
        if(left ==null||right==null){
            return false;
        }
        return (left.val == right.val)&&isMirror(left.left,right.right)&&isMirror(left.right,right.left);
    }
}

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

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
/**
 * 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 {
    private int[] preorder;
    private Map<Integer,Integer> inorderMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorderMap = new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            inorderMap.put(inorder[i],i);
        }
        return build(0,0,inorder.length-1);
    }
    private TreeNode build(int preStart,int inStart,int inEnd){
        if(inStart>inEnd){
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = inorderMap.get(rootVal);
        int leftSize = rootIndex-inStart;
        root.left = build(preStart+1,inStart,rootIndex-1);
        root.right = build(preStart+1+leftSize,rootIndex+1,inEnd);
        return root;
    }
}

使用hashMap来根据root的值得到该节点位于中序遍历的位置，然后切割为左右两个部分，递归寻找根节点。

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

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
import java.util.HashMap;

/**
 * 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 {
    private HashMap<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        int inRootIndex = inorderMap.get(rootVal);
        int leftSubtreeSize = inRootIndex - inStart;

        root.left = buildTreeHelper(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftSubtreeSize - 1);
        root.right = buildTreeHelper(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftSubtreeSize, postEnd - 1);

        return root;
    }
}

根据中序遍历，获得后序遍历顺序最左边到根节点的距离可以分为左右两段进行后续的处理。

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

这题好像不是前序也不是中序也不是后序遍历，新建一个数组吧，往里面填。

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Node dummy = new Node();
        Node curr = root;
        Node tail = dummy;
        while(curr!=null){
            if(curr.left!=null){
                tail.next=curr.left;
                tail=tail.next;
            }
            if(curr.right!=null){
                tail.next = curr.right;
                tail = tail.next;
            }
            curr=curr.next;
        }
        connect(dummy.next);
        return root;
    }
}

二叉树展开为链表

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
/**
 * 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 {
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        t(root,list);
        int size = list.size();
        for(int i = 1;i<size;i++){
            TreeNode prev = list.get(i-1);
            TreeNode curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }
    private void t(TreeNode root,List<TreeNode> list){
        if(root!=null){
            list.add(root);
            t(root.left,list);
            t(root.right,list);
        }
    }
}

路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        return c(root, 0, targetSum);
    }

    private boolean c(TreeNode root, int currentSum, int targetSum) {
        if(root == null) {
            return false;
        }
        
        currentSum += root.val;
        
        // Check if it's a leaf node
        if(root.left == null && root.right == null) {
            return currentSum == targetSum;
        }
        
        // Check left and right subtrees
        return c(root.left, currentSum, targetSum) || c(root.right, currentSum, targetSum);
    }
}

在return的时候进行递归。

求根节点到叶节点数字之和

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
/**
 * 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 {
    public int sumNumbers(TreeNode root) {
        return c(root,0); 
    }
    private int c(TreeNode root,int sum){
        if(root!=null){
            sum=root.val+sum*10;
            if(root.left==null&&root.right==null){
                return sum;
            }
            return c(root.left,sum)+c(root.right,sum);
        }
        return 0;
    }
}

如果为叶子节点就返回值，不然就继续递归。

二叉树中的最大路径和

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
/**
 * 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 {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        help(root);
        return maxSum;
    }
    private int help(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftMax = Math.max(0,help(root.left));
        int rightMax = Math.max(0,help(root.right));
        int currentSum = leftMax + rightMax +root.val;
        maxSum = Math.max(maxSum,currentSum);
        return root.val+Math.max(leftMax,rightMax);
    }
}

二叉搜索树迭代器

使用栈，通过弹出去当前节点的同时移动到右字数实现对整个树的遍历。

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
/**
 * 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 BSTIterator {
    private Stack<TreeNode> st = new Stack<>();

    public BSTIterator(TreeNode root) {
        pushAllLeft(root);
    }
    
    public int next() {
        TreeNode r = st.pop();
        pushAllLeft(r.right);
        return r.val;
    }
    
    public boolean hasNext() {
        return !st.isEmpty();
    }
    private void pushAllLeft(TreeNode node){
        while(node!=null){
            st.push(node); 
            node = node.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

完全二叉树的节点个数

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
/**
 * 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 {
    public int SUM = 0;
    public int countNodes(TreeNode root) {
        count(root);
        return SUM;
    }
    private void count(TreeNode node){
        if(node!=null){
            SUM++;
            count(node.left);
            count(node.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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，或者根节点等于 p 或者 q，直接返回根节点
        if (root == null || root == p || root == q) {
            return root;
        }
        // 递归遍历左子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归遍历右子树
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左子树和右子树都不为空，说明 p 和 q 分别在左右子树中，当前根节点就是最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 如果左子树不为空，说明 p 和 q 都在左子树中，返回左子树的结果
        return left != null ? 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
import java.util.ArrayList;
import java.util.List;

// 定义二叉树节点类
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 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 如果当前深度等于结果列表的大小，说明是该层的最右节点
        if (depth == result.size()) {
            result.add(node.val);
        }
        // 先递归遍历右子树
        dfs(node.right, depth + 1, result);
        // 再递归遍历左子树
        dfs(node.left, depth + 1, result);
    }
}

优先寻找右边，实现从左到右，如果找到了就不会结束，此时depth就会加一。返回值的类型可以看函数定义。

层序遍历

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
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 定义二叉树节点类
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 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return result;
    }
}

二叉树的层平均值