二叉树

二叉树的最大深度

原题链接:
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

相同的树

原题链接:
https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150

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 isSameTree(TreeNode p, TreeNode q) {
        if(p == null &&  q == null){
            return true;
        }

        if(p == null || q == null){
            return false;
        }

        if(p.val != q.val){
            return false;
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.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
/**
 * 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 TreeNode invertTree(TreeNode root) {
        return dfs(root);
    }

    private TreeNode dfs(TreeNode node){
        if(node == null){
            return null;
        }     

        TreeNode left = dfs(node.left);
        TreeNode right = dfs(node.right);

        node.left = right;
        node.right = left;

        return node;
    }
}

对称二叉树

原题链接:
https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-interview-150

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 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 boolean dfs(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }

        if(left == null ||  right == null){
            return false;
        }

        if(left.val != right.val){
            return false;
        }
        

        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }


    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return dfs(root.left,root.right);
    }
}

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

原题链接:
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0){
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[0]);

        for(int mid = 0 ; mid< inorder.length ; mid++){
            if(root.val == inorder[mid]){
                int [] pre_left = Arrays.copyOfRange(preorder,1,mid + 1);
                int [] pre_right = Arrays.copyOfRange(preorder,mid + 1, preorder.length);
                int [] in_left = Arrays.copyOfRange(inorder,0,mid);
                int [] in_right = Arrays.copyOfRange(inorder,mid + 1,inorder.length);
                
                root.left = buildTree(pre_left,in_left);
                root.right = buildTree(pre_right,in_right);
                // 加速 
                break;
            }
        }

        

        return root;
    }
}

写法2:
用hash存储 中序树中的节点关系 这样会更好一些 也会更快一些

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
/**
 * 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 {
    // 建立inorder中 值与位置的映射关系 便于后续的加速搜索
    HashMap<Integer,Integer> hash = new HashMap<>();
    private int [] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0 ; i < inorder.length ; i++){
            hash.put(inorder[i],i);
        }

        return dfs(0,0,preorder.length - 1);
    }

    private TreeNode dfs(int root,int left,int right){
        if(left > right){
            return null;
        }
        int val = preorder[root];
        TreeNode node = new TreeNode(val);
        int mid = hash.get(val);
        node.left = dfs(root + 1,left,mid - 1);
        // 根节点索引长度 + 左子树长度(mid - left) 的下一位 为右子树的根节点即为索引的起点
        node.right = dfs(root + mid - left + 1,mid + 1,right);

        return node;
    }
}

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

原题链接:
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 [] postorder;
    HashMap<Integer,Integer> hash = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        for(int i = 0 ; i < inorder.length ; i++){
            hash.put(inorder[i],i);
        }
        return dfs(inorder.length - 1,0,inorder.length - 1);
    }

    private TreeNode dfs(int root,int left,int right){
        if(left > right){
            return null;
        }

        int val = postorder[root];
        TreeNode node = new TreeNode(val);
        int mid = hash.get(val);
        node.right = dfs(root - 1,mid + 1,right);
        node.left = dfs(root - (right - mid) - 1,left,mid - 1);

        return node;
    }
}

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

原题链接:
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150

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
/*
// 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 {
    Queue<Node>q = new LinkedList<>();
     
    public Node connect(Node root) {
        if(root == null){
            return root;
        }

        q.offer(root);    

        while(!q.isEmpty()){
            int cur = q.size();
            ArrayList<Node> tmp = new ArrayList<>(q);
            for(int i = 0 ; i < cur ; i++){
               Node t = q.poll();

               if(t.left != null){
                q.offer(t.left);
               }

               if(t.right != null){
                   q.offer(t.right);
               }

                if(i == cur - 1){
                    t.next = null;
                    continue;
                }

               t.next = tmp.get(i + 1);               
            }
        }

        return root;
    }
}

二叉树展开为链表

原题链接:
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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) {
        while(root != null){
            // 左子树为空 那么直接不需要找了 跳到下一个节点即可
            if(root.left == null){
                root = root.right;
            }else{
                // 找到左子树 最右边节点的位置
                TreeNode insert = root.left;
                while(insert.right != null){
                    insert = insert.right;
                }
                insert.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
        }
    }
}

路径总和

原题链接:
https://leetcode.cn/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150

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 boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }

        // 已经是叶子节点 判断才成立
        if(root.val == targetSum && root.left == null && root.right == null){
            return true;
        }

        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }
}

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

原题链接:
https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 ans = 0;
    public int sumNumbers(TreeNode root) {
        if(root == null){
            return ans;
        }
        dfs(root,0);
        return ans;
    }

    // 上一个节点的值 
    void dfs(TreeNode node,int pre){
        if(node == null){
            return;
        }
        int cur = pre * 10 + node.val;
        // 如果当前为叶子节点 则进行操作
        if(node.left == null && node.right == null){
            ans += cur;
        }

        dfs(node.left,cur);
        dfs(node.right,cur);
    }
}

二叉树中的最大路径和

原题链接:
https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        int lr = root.val + Math.max(0,left) + Math.max(0,right);
        // 根到该节点的最大值
        int plr =  root.val + Math.max(0,Math.max(left,right));
        ans = Math.max(ans,Math.max(plr,lr));
        return plr;
    }
}

二叉搜索树迭代器

原题链接:
https://leetcode.cn/problems/binary-search-tree-iterator/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 {
    List<TreeNode> stk = new ArrayList<>();
    public BSTIterator(TreeNode root) {
        // 找到中序遍历第一个节点的位置
        dfsLeft(root);
    }
    
    public int next() {
        TreeNode node = stk.remove(stk.size() - 1);
        int res = node.val; 
        node = node.right;

        dfsLeft(node);
        return res;
    }
    
    public boolean hasNext() {
        return !stk.isEmpty();
    }

    private void dfsLeft(TreeNode root){
        while(root != null){
            stk.add(root);
            root = root.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();
 */

完全二叉树的节点个数

原题链接:
https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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 countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = countLevel(root.left);
        int right = countLevel(root.right);

        
        if(left == right){
            // 左右子树高度相同->证明左子树是满二叉树 直接计算得到 结果
            // 然后再递归去判断右子树的情况
            return countNodes(root.right) + (1 << left);
        }else{
            // 左右子树高度不同-> 肯定是左子树 > 右子树  -> 右子树比左子树少一层(完整的一层)  
            //  ->  统计右子树 -> 递归去计算左子树的情况
            return countNodes(root.left) + (1 << right);
        }
    }

    private int countLevel(TreeNode root){
        int h = 0;
        while(root != null){
            root = root.left;
            h++;
        }

        return h;
    }
}

二叉树的最近公共祖先

原题链接:
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

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
/**
 * 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) {
        // 当前节点为空 或者已经找到了节点 直接返回
        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 && right == null){
            return null;
        }

        // 只能在右子树中 同侧的情况
        if(left == null){
            return right;
        }

        if(right == null){
            return left;
        }

        return root;
    }
}

回溯

电话号码的字母组合

原题链接:
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-interview-150

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
class Solution {
    char [][] h = new char[][] {
            {},{},
            "abc".toCharArray(),
            "def".toCharArray(),
            "ghi".toCharArray(),
            "jkl".toCharArray(),
            "mno".toCharArray(),
            "pqrs".toCharArray(),
            "tuv".toCharArray(),
            "wxyz".toCharArray()
    };

    char [] dc;
    int n;
    List<String> ans = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        dc = digits.toCharArray();
        n = dc.length;

        if(n == 0){
            return ans;
        }

        dfs(0,new StringBuffer());
        return ans;
    }

    private void dfs(int i,StringBuffer sb){
        if (i == n){
            ans.add(sb.toString());
            return;
        }
        char [] letter = h[dc[i] - '0'];
        for (int k = 0; k < letter.length; k++){
            sb.append(letter[k]);
            dfs(i + 1,sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

组合

原题链接:
https://leetcode.cn/problems/combinations/description/?envType=study-plan-v2&envId=top-interview-150

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int n,k;
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        dfs(1,new ArrayList<Integer>());
        return ans;
    }

    private void dfs(int cur,List<Integer> arr){
        if(arr.size() == k){
            ans.add(new ArrayList<>(arr));
            return;
        }

        for(int i = cur ; i <= n ; i++){
            arr.add(i); 
            dfs(i + 1,arr);
            arr.remove(arr.size() - 1);
        }
    }
}

全排列

原题链接:
https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-interview-150

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
class Solution {
    int [] q;
    int n;
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        q = nums;
        n = q.length;

        dfs(new ArrayList<Integer>());
        return ans;
    }

    private void dfs(List<Integer> arr){
        if(arr.size() == n){
            ans.add(new ArrayList<>(arr));
            return;
        }

        for(int i = 0 ; i < n ; i++){
            if(arr.contains(q[i])){
                continue;
            }

            arr.add(q[i]);
            dfs(arr);
            arr.remove(arr.size() - 1);
        }
    }
}

组合总和

原题链接:
https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-interview-150

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
class Solution {
    int [] cand;
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        cand = candidates;
        dfs(0,target,new ArrayList<>());
        return ans;
    }

    private void dfs(int cur,int tar,List<Integer> arr){
        if(tar == 0){
            ans.add(new ArrayList<Integer>(arr));
            return;
        }

        for(int i = cur ; i < cand.length ; i++){
            if(tar - cand[i] < 0){
                continue;
            }
            arr.add(cand[i]);
            tar -= cand[i];
            dfs(i,tar,arr);
            tar += cand[i];
            arr.remove(arr.size() - 1);
        }
    }
}