Leetcode日记(三)

二叉树

在开始二叉树之前，我们先复习两种较为少用的数据结构 Queue 和 Stack.

Queue 是java.util下的一个interface,集成了collections接口，该接口有如下方法:

  • add()/offer(): 用于向队尾添加数据， 区别: 添加失败时add方法throw异常 offer return false
  • remove()/poll(): 用于从队头删除元素 并返回数据，区别同上
  • element()/peek(): 用于从队首返回数据 区别同上
    Queue的继承实现关系如下表:

java集合类继承关系图

注:

  • LinkedList : 常用的基本队列
  • ArrayQueue: 常用的双端队列
  • PriorityQueue: 常用的优先级队列
    Stack继承了Vector，但是Vector并不常用，Stack中的方法如下:
  • push()
  • pop()
  • peek()
  • empty()
  • search(): 序号为距离栈顶的距离，找不到则返回-1
    注:
    Stack和Stack一样不被建议使用，建议使用Deque下的ArrayDeque和LinkedList充当栈。

二叉树的深度优先遍历方式(递归版本)

前序遍历: 

1
2
3
4
5
6
7
8
private List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) return list;
    list.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return list;
}

中序遍历：

1
2
3
4
5
6
7
8
private List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) return list;
    inorderTraversal(root.left);
    list.add(root.val);
    inorderTraversal(root.right);
    return list;
}

后序遍历:

1
2
3
4
5
6
7
8
private List<Integer> list = new ArrayList<>();
public List<Integer>  postorderTraversal(TreeNode root) {
    if (root == null) return list;
     postorderTraversal(root.left);
     postorderTraversal(root.right);
     list.add(root.val);
    return list;
}

二叉树的深度优先遍历(迭代版)

前序遍历: 

1
2
3
4
5
6
7
8
9
10
11
12
13
private List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        if (root == null) return list;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode p = stack.pop();
            list.add(p.val);
            if (p.right != null) stack.push(p.right);
            if (p.left != null) stack.push(p.left);
        }
        return list;
    }

中序遍历: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        if (root == null) return list;
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                list.add(p.val);
                p = p.right;
            }
        }
        return list;
    }

后序遍历: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer>  postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack();
    if (root == null) return list;
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode p = stack.pop();
        list.add(p.val);
        if (p.left != null) stack.push(p.left);
        if (p.right != null) stack.push(p.right);
    }
    Collections.reverse(list);
    return list;
    }

二叉树的广度优先遍历(层次遍历)

LeetCode102: 二叉树的层次序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) return list;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode p = queue.poll();
                path.add(p.val);
                if (p.left != null) queue.offer(p.left);
                if (p.right != null) queue.offer(p.right);
                size--;
            }
            list.add(new ArrayList<>(path));
            path.clear();
        }
        return list;
    }

LeetCode102: 对称二叉树

迭代法: 

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
public boolean isSymmetric(TreeNode root) {
         return check(root, root);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode p = null, q = null;
        queue.offer(left);
        queue.offer(right);
        while (!queue.isEmpty()) {
            p = queue.poll();
            q = queue.poll();
            if (p == null && q == null) {
                continue;
            }
            if (p == null && q != null || p != null && q == null || p.val != q.val) {
                return false;
            }
            queue.offer(p.left);
            queue.offer(q.right);
            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }

LeetCode105: 由中序遍历&前序遍历唯一确定一颗二叉树

递归方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private HashMap<Integer, Integer> hp = new HashMap<>();

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

    private TreeNode buildMyTree(int[] preorder, int[] inorder,int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return null;
        if (preLeft == preRight) return new TreeNode(preorder[preLeft]);
        TreeNode root = new TreeNode(preorder[preLeft]);
        int index = hp.get(root.val);
        int len = index - inLeft;
        root.left = buildMyTree(preorder, inorder, preLeft + 1, preLeft + len , inLeft,  index - 1);
        root.right = buildMyTree(preorder, inorder, preLeft + len + 1, preRight, index + 1, inRight);
        return root;
    }

LeetCode106: 从中序遍历和后序遍历构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildMyTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode buildMyTree(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (postStart > postEnd) return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = findIndex(inorder, root.val);
        root.left = buildMyTree(inorder, postorder, inStart, index - 1, postStart, index - 1 - inStart + postStart);
        root.right = buildMyTree(inorder, postorder, index + 1, inEnd, index - inStart + postStart, postEnd - 1);
        return root;
    }

    private int findIndex(int[] inorder, int target) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == target) return i;
        }
        return  -1;
    }

LeetCode654: 最大二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildMyTree(nums, 0, nums.length - 1);
    }

private TreeNode buildMyTree(int[] nums, int start, int end) {
    if (start > end) return  null;
    int index = findMax(nums, start, end);
    TreeNode root = new TreeNode(nums[index]);
    root.left = buildMyTree(nums, start, index -1);
    root.right = buildMyTree(nums, index + 1, end);
    return root;
}

private int findMax(int[] nums, int start, int end) {
    int max= nums[start];
    int index = start;
    for (int i = start; i <= end ; i++) {
        if (nums[i] > max) {
            max = nums[i];
            index = i;
        }
    }
    return index;
}

LeetCode257: 二叉树的所有路径

递归+回溯

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
private List<String> result = new ArrayList<>();
    private List<List<Integer>> list = new ArrayList<>();
    private  LinkedList<Integer> path = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;
        backtracking(root);
        for (List<Integer> integers : list) {
            StringJoiner sj = new StringJoiner("->");
            for (Integer integer : integers) {
                sj.add(Integer.toString(integer));
            }
            result.add(sj.toString());
        }
        return result;
    }

    private void backtracking(TreeNode root) {
        path.add(root.val);
        if (root.left != null)backtracking(root.left);
        if (root.right != null) backtracking(root.right);
        if (root.left == null && root.right == null) {
            list.add(new ArrayList<>(path));
        }
        path.removeLast();
    }

LeetCode112: 路径总和

递归＋回溯算法: 

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

    private void backtracking(TreeNode root, int targetSum) {
        if (root.left == null && root.right == null &&  sum + root.val == targetSum) {
            flag = true;
            return;
        }
        TreeNode p = root;

        sum += p.val;
        if (p.left != null) backtracking(p.left, targetSum);
        if (p.right != null) backtracking(p.right, targetSum);
        sum -= p.val;

    }

LeetCode501: 二叉搜索树中的众数

双指针法: 

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
private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null, cur = root;
        int maxCount = 0, count = 0;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {            
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre == null || pre.val != cur.val) {
                    count = 1;
                } else {
                    count++;
                }
                if (count > maxCount) {
                    list.clear();
                    list.add(cur.val);
                    maxCount = count;
                } else if (count == maxCount) {
                    list.add(cur.val);
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

LeetCode236: 寻找二叉树的公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List<List<TreeNode>> result = new ArrayList<>();
    LinkedList<TreeNode> path = new LinkedList<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        backtracking(root, p, q);
        List<TreeNode> list1 = result.get(0);
        List<TreeNode> list2 = result.get(1);
        int i = 0;
        while (i < list1.size() && list1.get(i) == list2.get(i)) {
            i++;
        }
        return list1.get(i - 1);
    }

    private void backtracking(TreeNode root, TreeNode p, TreeNode q) {
        if (result.size() == 2) return;
        path.add(root);
        if (root == p || root == q) {
            result.add(new ArrayList<>(path));
        }
        if (root.right != null) backtracking(root.right, p, q);
        if (root.left != null) backtracking(root.left, p, q);
        path.removeLast();
    }

LeetCode450: 二叉搜索树的删除操作

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
public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        TreeNode pre = null, cur = root;
        while (cur != null) {
            if (cur.val > key) {
                pre = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                pre = cur;
                cur = cur.right;
            } else {
                if (pre == null) {
                    if (cur.left == null){
                        return cur.right;
                    } else if (cur.right == null) {
                        return cur.left;
                    }
                    pre = cur.right;
                    root = pre;
                    TreeNode p = cur.left;
                    cur = cur.right;
                    while (cur.left != null) {
                        cur = cur.left;
                    }
                    cur.left = p;
                } else if (pre.left == cur) {
                    if (cur.left == null) {
                        pre.left = cur.right;
                    } else if (cur.right == null) {
                        pre.left = cur.left;
                    } else {
                        pre.left = cur.right;
                        TreeNode p = cur.left;
                        cur = cur.right;
                        while (cur.left != null) {
                            cur = cur.left;
                        }
                        cur.left = p;
                    }
                } else if (pre.right == cur){
                    if (cur.left == null) {
                        pre.right = cur.right;
                    } else if (cur.right == null) {
                        pre.right = cur.left;
                    } else {
                        pre.right = cur.right;
                        TreeNode p = cur.left;
                        cur = cur.right;
                        while (cur.left != null) {
                            cur = cur.left;
                        }
                        cur.left = p;
                    }
                }
                break;
            }
        }
        return root;
    }

LeetCode699: 修剪二叉搜索树
递归法: 

1
2
3
4
5
6
7
8
9
10
11
public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

LeetCode437: 路径总和Ⅲ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private int count = 0;
    private long sum = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode p = stack.pop();
            backtracking(p, targetSum);
            if (p.right != null) stack.push(p.right);
            if (p.left != null) stack.push(p.left);
        }
        
        return count;
    }

    private void backtracking(TreeNode root, int targetSum) {
        sum += root.val;
        if (sum == targetSum) count++;
        if (root.left != null) backtracking(root.left, targetSum);
        if (root.right != null) backtracking(root.right, targetSum);
        sum -= root.val;
    }
Leetcode
#代码练习日记
Leetcode日记(三)
http://example.com/2023/10/28/Leetcode日记(三)/
作者
John Doe
发布于
2023年10月28日
许可协议