leetcode - 03 树专题 450~230~572~208~100~剑指Offer 32~剑指Offer 33

剑指 Offer 33. 二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length == 0){
            return true;
        }
        // 递归判断此数组是否是二叉树的后续遍历序列
        return dfs(postorder,0,postorder.length-1);
    }

    private boolean dfs(int[] postorder, int left, int right) {
        // 对于二叉搜索树：左子树的节点都小于根节点，右子树的节点都大于根节点
        if(left>=right){
            return true;
        }

        // 根节点的值
        int rootValue = postorder[right];

        // 找到第一个比根节点大的数的索引（说明左侧的数都比根节点小）
        int index = 0;
        while (postorder[index]<rootValue){
            index++;
        }

        // 暂存索引
        int maxIndex = index;

        // 判断右子树的节点是否都比根节点大
        while (postorder[index]>rootValue){
            index++;
        }

        // 判断是后序序列否满足左右子树
        return index==right && dfs(postorder,left,maxIndex-1) && dfs(postorder,maxIndex,right-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

100. 相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 相同的树：结构相同，节点的值相同
        if(p==null && q==null){
            return true;
        }
        if(p==null || q==null){
            return false;
        }

        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

剑指 Offer 32 - III. 从上到下打印二叉树 III

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                if(level % 2 == 1){
                    list.add(node.val);
                }else {
                    list.add(0,node.val);
                }
            }
            level++;
            res.add(list);
        }
        return res;
    }
}
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

450. 删除二叉搜索树中的节点

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if(key>root.val){
            // 如果目标节点大于当前节点，去右子树中删除
            root.right = deleteNode(root.right,key);
        }else if(key<root.val){
            // 如果目标节点小于当前节点，去左子树中删除
            root.left = deleteNode(root.left,key);
        }else{
            // 如果目标节点是当前节点
            // 如果删除的节点没有左子树，则右子树顶替其位置，删除该节点
            if(root.left==null){
                return root.right;
            }
            // 如果删除的节点没有右子树，则左子树顶替其位置，删除该节点
            if(root.right==null){
                return root.left;
            }
            // 如果删除的节点左右子树都有，则左子树转移到右子树的最左节点的左子树上，然后右子树顶替其位置，删除该节点
            else if(root.left!=null && root.right!=null){
                TreeNode node = root.right;
                // 寻找右子树的最左节点
                while (node.left!=null){
                    node = node.left;
                }
                node.left = root.left;
                return root.right;
            }
        }
        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

230. 二叉搜索树中第K小的元素

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.left;
            }
           root = stack.pop();
            k--;
            if(k==0){
                break;
            }
            root = root.right;
        }
        return root.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

572. 另一棵树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot==null){
            return true;
        }
        if(root==null){
            return false;
        }
        return dfs(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    // 判断两个树是否相同
    private boolean dfs(TreeNode root, TreeNode subRoot) {
        if(root==null && subRoot==null){
            return true;
        }
        if(root==null || subRoot==null){
            return false;
        }
        return root.val== subRoot.val && dfs(root.left,subRoot.left) && dfs(root.right,subRoot.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

208. 实现 Trie (前缀树)

https://leetcode.cn/problems/implement-trie-prefix-tree/solution/fu-xue-ming-zhu-cong-er-cha-shu-shuo-qi-628gs/

class Trie {

    private TrieNode root;

    /**
     * 定义前缀树的数据结构
     */
    static class TrieNode{
        boolean isWorld;
        TrieNode[] child = new TrieNode[26];
        public TrieNode(){
            this.isWorld = false;
        }
    }

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode p = root;
        int len = word.length();
        for(int i=0;i<len;i++){
            int t = word.charAt(i)-'a';
            if(p.child[t]==null){
                p.child[t] = new TrieNode();
            }
            p = p.child[t];
        }
        p.isWorld = true;
    }
    
    public boolean search(String word) {
        TrieNode p = root;
        int len = word.length();
        for(int i=0;i<len;i++){
            int t = word.charAt(i)-'a';
            if(p.child[t]==null){
                return false;
            }
            p = p.child[t];
        }
        return p.isWorld;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        int len = prefix.length();
        for(int i=0;i<len;i++){
            int t = prefix.charAt(i)-'a';
            if(p.child[t]==null){
                return false;
            }
            p = p.child[t];
        }
        return true;
    }
}
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