Leetcode Notes

代码随想录刷题笔记

Posted on Edited on In

669 修剪二叉搜索树

给定最大边界，和最小边界，确保二叉搜索树的结点值在最大边界和最小边界之中，返回修剪好的树的节点
重构二叉树时，把给节点的父节点的左子树连接到删除之后的节点中

递归法

root小于low，就要找大于low 的值修剪右子树
root大于high，就要找小于high的值修剪左子树

root的left，就要修剪左树
root的right，修剪右树
之后返回root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        if (root.val < low) return trimBST(root.right, low, high);
        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;
    }
}

迭代法

剪枝时分三步
将root移动到L和R范围内
剪枝左子树，剪枝右子树

先找到root在L 和 R 范围中的结点
找左边的所有小于L的节点，小于L 则该节点左子树应该全部删掉，只保留右子树
找右边的所有大于R的节点，同理大于R则该节点右子树应该全部删掉，只保留左子树

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
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        while (root != null && (root.val < low || root.val > high)){
            if (root.val < low){
                root = root.right;
            } else {
                root = root.left;
            }
        }

        TreeNode cur = root;

        while (cur != null){
            while (cur.left != null && cur.left.val < low){
                cur.left = cur.left.right;
            }

            cur = cur.left;
        }

        cur = root;

        while (cur != null){
            while (cur.right != null && cur.right.val > high){
                cur.right = cur.right.left;
            }

            cur = cur.right;
        }

        return root;
    }
}

108 将有序数组转换为二叉搜索树

递归分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildHelper(nums, 0, nums.length);
    }

    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int midIndex = start + ((end - start) >> 1);
        int midValue = nums[midIndex];

        TreeNode root = new TreeNode(midValue);

        root.left = buildHelper(nums, start, midIndex);
        root.right = buildHelper(nums, midIndex + 1, end);

        return root;
    }
}

538 把二叉搜索树转换成累加树

题目里是右中左的顺序，也就是反中序遍历变换而成的累加树

在递归中添加sum累加node的值，在赋给root的值上

最后遍历整个树就会获得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        root.right = convertBST(root.right);

        sum += root.val;
        root.val = sum;

        root.left = convertBST(root.left);
        return root;
    }
}

复习

二叉树深度遍历

递归
后序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return result;

        postorder(root);

        return result;
    }

    private void postorder(TreeNode root){
        if (root == null) return;

        postorder(root.left);
        postorder(root.right);
        result.add(root.val);
    }
}

迭代
前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(result);
        return result;
    }
}

统一迭代
后序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                stack.push(node);
                stack.push(null);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }
        return result;
    }
}

dfs

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 {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;

        dfs(root, 0);

        return result;
    }

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (depth > result.size()){
            result.add(new ArrayList<Integer>());
        }

        result.get(depth - 1).add(root.val);

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

二叉树层序遍历

bfs

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int length = queue.size();

            while (length-- > 0){
                TreeNode node = queue.poll();
                
                item.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(item);
        }

        return result;
    }
}

226 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        swapChildren(root);

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    private void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

101 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right,right.left);

        return compareOutside && compareInside;
    }
}

104 二叉树最大深度

1
2
3
4
5
6
7
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

111 二叉树最小深度

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root,0);
        return minDepth;
    }

    private void dfs(TreeNode root, int depth){
        depth++;
        if (root.left == null && root.right == null){
            if (depth < minDepth){
                minDepth = depth;
            }
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right,depth);
    }
}

层序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            depth++;
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

222 完全二叉树节点个数

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
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = 0;
        int rightDepth = 0;
        while (left != null){
            left = left.left;
            leftDepth++;
        }

        while(right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

110 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root){
        if (root == null) return 0;

        int left = getHeight(root.left);
        if (left == -1) return -1;
        int right = getHeight(root.right);
        if (right == -1) return -1;
    
        if (Math.abs(left - right) > 1){
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

257 二叉树的所有路径

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
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();
        getPaths(root, paths);
        return result;
    }

    private void getPaths(TreeNode root, List<Integer> paths){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }   

            sb.append(paths.get(paths.size() - 1));

            result.add(sb.toString());
            return;
        }

        if (root.left != null){
            getPaths(root.left, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null){
            getPaths(root.right, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

404 左叶子之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return sum;
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int depth){
        depth++;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

简便写法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }
        if (root.left != null) sumOfLeftLeaves(root.left);
        if (root.right != null) sumOfLeftLeaves(root.right);

        return sum;
    }
}

513 找树左下角的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int maxDepth = 0;
    int result = 0;
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        return result;
    }

    private void dfs(TreeNode root, int depth){
        depth++;

        if (root.left == null && root.right == null && depth > maxDepth){
            result = root.val;
            maxDepth = depth;
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

112 路径总和

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

    private boolean getPaths(TreeNode root, int targetSum){
        if (root == null) return false;
        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0) return true;
            else return false;
        }

        boolean left = getPaths(root.left, targetSum);
        boolean right = getPaths(root.right, targetSum);

        return left || right;
    }
}

113 路径总和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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;

        List<Integer> path = new ArrayList<>();

        getPath(root, targetSum, path);

        return result;
    }

    private void getPath(TreeNode root, int targetSum, List<Integer> path){
        path.add(root.val);
        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0){
                result.add(new ArrayList<Integer>(path));
                return;
            }
        }

        if (root.left != null){
            getPath(root.left, targetSum, path);
            path.remove(path.size() - 1);
        }
        if (root.right != null){
            getPath(root.right, targetSum, path);
            path.remove(path.size() - 1);
        }
    }
}

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

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 {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        int count = 0;
        for (int i : inorder){
            map.put(i, count++);
        }
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS >= inE || postS >= postE) return null;
        int rootVal = postorder[postE - 1];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lenOfLeft);
        root.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lenOfLeft, postE - 1);

        return root;
    }
}

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

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 {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0) return null;
        int count = 0;
        for (int i : inorder){
            map.put(i, count++);
        }
        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;
        int rootVal = preorder[preS];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(preorder, preS + 1, preS + 1 + lenOfLeft, inorder, inS, rootIndex);
        root.right = buildHelper(preorder, preS + 1 + lenOfLeft, preE, inorder, rootIndex + 1, inE);

        return root;
    }
}

654 最大二叉树

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
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums){
        if (nums.length == 0) return null;
        return buildHelper(nums, 0, nums.length);
    }

    private int[] getMaximum(int[] nums, int start, int end){
        int[] result = new int[2];
        result[0] = Integer.MIN_VALUE;
        result[1] = -1;
        for (int i = start; i < end; i++){
            if (nums[i] > result[0]){
                result[0] = nums[i];
                result[1] = i;
            }
        }
        return result;
    }

    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int[] maxArray = getMaximum(nums, start, end);
        int rootVal = maxArray[0];
        int rootIndex = maxArray[1];

        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(nums, start, rootIndex);
        root.right = buildHelper(nums, rootIndex + 1, end);

        return root;
    }
}

617 合并二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null && root2 != null) return root2;
        if (root1 != null && root2 == null) return root1;
        TreeNode root = new TreeNode(root1.val + root2.val);
        

        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);

        return root;  
    }
}

700 二叉搜索树中的搜索

1
2
3
4
5
6
7
8
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        else if (root.val > val) return searchBST(root.left, val);
        else return searchBST(root.right, val);
    }
}

98 验证二叉搜索树

注意对比返回left的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean left = isValidBST(root.left);
        if (!left) return false;
        
        if (pre != null && pre.val >= root.val) return false;
        pre = root;

        boolean right = isValidBST(root.right);

        return right;
    }
}

107 二叉树的层次遍历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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            List<Integer> item = new ArrayList<>();
            while(length-- > 0){
                TreeNode node = queue.poll();
                item.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(item);
        }

        Collections.reverse(result);

        return result;
    }
}

199 二叉树的右视图

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 {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (length == 0){
                    result.add(node.val);
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return result;
    }
}

530 二叉搜索树的最小绝对差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    TreeNode pre;
    int minDiff = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;

        getMinimumDifference(root.left);
        if (pre != null && root.val - pre.val < minDiff){
            minDiff = root.val - pre.val;
        }

        pre = root;

        getMinimumDifference(root.right);

        return minDiff;
    }
}

501 二叉搜索树中的众数

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
class Solution {
    int maxCount = 0;
    int count = 0;
    List<Integer> result = new ArrayList<>();
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] res = new int[result.size()];
        int count = 0;
        for (int i : result){
            res[count++] = i;
        }

        return res;
    }

    private void inorder(TreeNode root){
        if (root == null) return;
        inorder(root.left);

        if (pre == null || pre.val != root.val){
            count = 1;
        } else {
            count++;
        }

        if (maxCount < count){
            result.clear();
            result.add(root.val);
            maxCount = count;
        } else if (count == maxCount){
            result.add(root.val);
        }

        pre = root;
        inorder(root.right);
    }
}

236 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);

        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null && right != null) return right;
        else if (left != null && right == null) return left;
        else if (left != null && right != null) return root;
        else return null;
    }
}

235 二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        
        if (p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        if (root.val >= p.val && root.val <= q.val) return root;
        else if (root.val < p.val) return lowestCommonAncestor(root.right, p, q);
        else return lowestCommonAncestor(root.left, p, q);
    }
}

701 二叉搜索树中插入

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (root.val < val) root.right = insertIntoBST(root.right, val);
        if (root.val > val) root.left = insertIntoBST(root.left, val);

        return root;
    }
}

450 删除二叉搜索树中的结点

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
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val == key){
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null){
                    cur = cur.left;
                }

                cur.left = root.left;
                root = root.right;

                return root;
            }
        }

        if (root.val < key) root.right = deleteNode(root.right, key);
        if (root.val > key) root.left = deleteNode(root.left, key);
        return root;
    }
}


669 修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        if (root.val < low) return trimBST(root.right, low, high);
        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;
    }
}

108 将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return buildHelper(nums, 0, nums.length);
    }
    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int midIndex = start + ((end - start) >> 1);
        int midValue = nums[midIndex];

        TreeNode root = new TreeNode(midValue);

        root.left = buildHelper(nums, start, midIndex);
        root.right = buildHelper(nums, midIndex + 1, end);

        return root;
    }
}

538 把二叉搜索树转换成累加树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        return revertInorder(root);
    }

    private TreeNode revertInorder(TreeNode root){
        if (root == null) return null;
        revertInorder(root.right);
        sum += root.val;
        root.val = sum;
        revertInorder(root.left);

        return root;
    }
}

Posted on In

235 二叉搜索树的最近公共祖先

复习 236 二叉树的最近公共祖先

利用后序遍历整个二叉树

记住回溯过程
左边有返回左边，右边有返回右边，两边都有返回中间，两边都没有就是null，最后回溯到最后搜到了就有值
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == q || root == p) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;
    if (left != null && right == null) return left;

    else if (left == null && right != null) return right;
    else return null;
}

}

此题利用二叉搜索树的特点，不需要自下而上遍历，因为公共祖先一定是在p和q之间的值，那么自上而下遍历二叉树，找到的第一个p和q的中间值的位置就是他们的最近公共祖先

自己利用dfs记录深度，返回root

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 {
    TreeNode result;
    int minDepth = Integer.MAX_VALUE;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, 0, p, q);
        return result;
    }

    private void dfs(TreeNode root, int depth, TreeNode p, TreeNode q){
        depth++;

        if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >=q.val)){
            if (depth < minDepth){
                minDepth = depth;
                result = root;
            }
        } 

        if (root.left != null) dfs(root.left, depth, p, q);
        if (root.right != null) dfs(root.right, depth, p, q);
    }
}

简便写法，如果root值比两个值都大，就在root.left, 如果root值比两个值都小，就在root.right, 剩余的情况就是root

1
2
3
4
5
6
7
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        else if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        else return root;
    }
}

迭代

只需要在root值在p和q中间时即可返回root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (true){
            if (root.val > p.val && root.val > q.val){
                root = root.left;
            } else if (root.val < p.val && root.val < q.val){
                root = root.right;
            } else {
                break;
            }
        }

        return root;
    }
}

701 二叉搜索树中插入

如果不考虑重构二叉树，只需要找到空节点并且插入所需节点即可，遍历二叉搜索树时

遇到null值建立新TreeNode, 只比较root和val的值即可，root > val 构建左树，root < val 构建右树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (root.val > val) root.left = insertIntoBST(root.left, val);
        if (root.val < val) root.right = insertIntoBST(root.right, val);

        return root;
    }
}

迭代法就是遍历父节点，找到位置

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

删除二叉搜索树节点中需要重构二叉树

有五种情况：

  1. 没找到删除的节点，遍历到空节点返回
  2. 左右孩子都为空，直接删除节点
  3. 删除节点左孩子为空，右孩子不为空，删除节点，右孩子补位
  4. 删除节点右孩子为空，左孩子不为空，删除节点，左孩子补位
  5. 左右孩子都不为空，将删除节点的左子树头节点放到删除节点的右子树最左面节点的左孩子上，返回删除节点右孩子为新根节点
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
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;

        if (root.val == key){
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null){
                    cur = cur.left;
                }

                cur.left = root.left;
                root = root.right;

                return root;
            }
        }

        if (root.val > key) root.left = deleteNode(root.left, key);
        if (root.val < key) root.right = deleteNode(root.right, key);

        return root;
    }
}

Posted on Edited on In

203 移除链表元素

利用dummy node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;

        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null){
            if (cur.val == val){
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }

        return dummy.next;
    }
}

利用递归
判断返回条件，把下一个值做成条件，确定一个循环的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;

        head.next = removeElements(head.next,val);
        if (head.val == val){
            return head.next;
        } else {
            return head;
        }
    }
}

707 设计链表

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
61
62
63
64
65
66
67
68
69
70
71
72
73
class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }
}


class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index > size - 1){
            return -1;
        }

        ListNode cur = head;

        for (int i = 0; i <= index; i++){
            cur = cur.next;
        }

        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0) index = 0;
        if (index > size) return;
        size++;
        ListNode newNode = new ListNode(val);
        ListNode pre = head;

        for (int i = 0; i < index; i++){
            pre = pre.next;
        }

        newNode.next = pre.next;
        pre.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) return;

        size--;

        ListNode pre = head;

        for (int i = 0; i < index; i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}

206 翻转链表

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;

        ListNode cur = head;

        while (cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode prev){
        if (cur == null) return prev;

        ListNode temp = cur.next;
        cur.next = prev;

        return reverse(temp, cur);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;

        ListNode next = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return next;
    }
}

24 两两交换链表中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null){
            ListNode firstNode = cur.next;
            ListNode secondNode = cur.next.next;
            ListNode temp = cur.next.next.next;
            cur.next = secondNode;
            secondNode.next = firstNode;
            firstNode.next = temp;
            cur = firstNode;
        }

        return dummy.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode next = head.next;
        ListNode newNode = swapPairs(next.next);

        next.next = head;
        head.next = newNode;

        return next;
    }
}

19 删除链表的倒数第N个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
	public ListNode removeNthFromEnd(ListNode head, int n){
		ListNode dummy = new ListNode(0, head);
		
		ListNode slowIndex = dummy;
		ListNode fastIndex = dummy;
		
		for (int i = 0; i <= n; i++) fastIndex = fastIndex.next;

		while(fastIndex != null){
			fastIndex = fastIndex.next;
			slowIndex = slowIndex.next;
		}
		
		slowIndex.next = slowIndex.next.next;
		
		return dummy.next;
	}
}

160 链表相交

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

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenHeadA = 0;
        int lenHeadB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != null){
            lenHeadA++;
            curA = curA.next;
        }

        while (curB != null){
            lenHeadB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if (lenHeadA > lenHeadB){
            for (int i = 0; i < lenHeadA - lenHeadB; i++){
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < lenHeadB - lenHeadA; i++){
                curB = curB.next;
            }
        }

        while (curA != null){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }
}

142 链表相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow){
                ListNode cur = head;
                while (cur != slow){
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
        return null;
    }
}

Posted on Edited on

704 二分查找

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] > target){
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return -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
class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target){
                return mid;
            } else if (target < nums[mid]){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

35 搜索插入位置

二分查找，输出mid或左值

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 {
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target) {
                return mid;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

34 在排序数组中查找元素的第一个和最后一个位置

在数组中找到位置，然后滑动左右指针找到

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[] {-1, -1};
        int index = binarySearch(nums, target);
        if (index == -1) return new int[] {-1, -1};
        else {
            int left = index;
            int right = index;

            for (int i = index; i >= 0; i--){
                if (nums[i] == target) left--;
            }

            for (int i = index; i < nums.length; i++){
                if (nums[i] == target) right++;
            }

            return new int[] {left + 1, right - 1};

        }
        
    }
    private int binarySearch(int[] nums, int target){
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            if (nums[mid] == target){
                return mid;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return -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
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[] {getLeftBorder(nums, target), getRightBorder(nums, target)};
    }

    private int getLeftBorder(int[] nums, int target){
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target){
                for (int i = mid; i >= left; i--){
                    if (nums[mid] == target) mid--;
                }

                return mid + 1;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        } 

        return -1;
    }

    private int getRightBorder(int[] nums, int target){
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target){
                for (int i = mid; i < right; i++){
                    if (nums[mid] == target) mid++;
                }

                return mid - 1;
            } else if (target > nums[mid]){
                left = mid + 1;
            } else {
                right = mid;
            }
        } 

        return -1;
    }
}

69 x的平方根

注意返回的数字 是 右 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;

        int left = 0;
        int right = x;
        while (left < right){
            int mid =  left + ((right - left) >> 1);
            long midSquare = (long) mid * mid;
            if (midSquare == (long) x){
                return mid;
            } else if (midSquare < x){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right - 1;
    }
}

367 有效的完全平方数

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


class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 0 || num == 1) return true;

        int left = 0;
        int right = num;

        while (left < right){
            int mid = left + ((right - left) >> 1);

            long midS = (long) mid * mid;

            if (midS == (long) num) {
                return true;
            } else if (midS < num){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return false;
    }
}

27 移除元素

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;

        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if (nums[fastIndex] != val){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
}

左右指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;

        for (left = 0; left <= right; left++){
            if (nums[left] == val){
                nums[left] = nums[right--];
                left--;
            }
        }

        return left;
    }
}

26 删除排序数组中的重复项

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int removeDuplicates(int[] nums) {
        int fastIndex = 0;
        int slowIndex = 1;

        for (fastIndex = 1; fastIndex< nums.length; fastIndex++){
            if (nums[fastIndex] != nums[slowIndex - 1]){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }

        return slowIndex;
        
    }
}

283 移动零

快慢指针的另种用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void moveZeroes(int[] nums) {
        int fastIndex = 0;
        int slowIndex = 0;

        for (fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if (nums[fastIndex] != 0){
                nums[slowIndex++] = nums[fastIndex];
            }
        }

        for (int i = slowIndex; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}

844 比较含退格的字符串

利用stringbuilder

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 backspaceCompare(String s, String t) {
        s = getString(s);
        t = getString(t);
        return s.equals(t);
    }

    private String getString(String s){
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char i : chars){
            if (i == '#'){
                if (sb.length() != 0){
                    sb.delete(sb.length() - 1, sb.length());
                }
            } else {
                sb.append(i);
            }
        }

        return sb.toString();
    }
}

977 有序数组的平方

左右指针

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 int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while (left <= right){
            int leftS =  nums[left] * nums[left];
            int rightS =  nums[right] * nums[right];

            if (leftS <= rightS) {
                result[index--] = rightS;
                right--;
            }
            else {
                result[index--] = leftS; 
                left++;
            }
        }

        return result;
    }
}

209 长度最小的子数组

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (right = 0; right < nums.length; right++){
            sum += nums[right];
            while (sum >= target){
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

904 水果成篮

利用HashMap计数，然后在hashmap里面为0时删除
记录length 比较最长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();

        int left = 0; 
        int right = 0;
        for (right = 0; right < fruits.length; right++) {
            map.put(fruits[right], map.getOrDefault(fruits[right],0) + 1);
            while (map.size() > 2){
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            result = Math.max(result, right - left + 1);
        }
            return result;
        } 
        
}

76 最小覆盖子串

利用两个hashmap记录次数，

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
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char i : t.toCharArray()){
            need.put(i, need.getOrDefault(i, 0) + 1);
        }

        int left = 0, right = 0;
        // valid character count;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }

            while (valid == need.size()){
                if (right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);

                left++;

                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }

                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

59 螺旋矩阵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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int start = 0;
        int count = 1;
        int offset = 1;
        int loop = n / 2;
        int i = 0, j = 0;
        while (loop-- > 0){
            for (j = start; j < n - offset; j++){
                result[start][j] = count++;
            }

            for (i = start; i < n - offset; i++){
                result[i][j] = count++;
            }

            for (;j > start; j--){
                result[i][j] = count++;
            }

            for (;i > start; i--){
                result[i][j] = count++;
            }
            start++;
            offset++;
        }

        if (n % 2 == 1){
            result[start][start] = count;
        }

        return result;

    }
}

54 螺旋数组

此时由于数组不规则，不适用规则上面的规则

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
       List<Integer> list = new ArrayList();
        int m = matrix.length, n = matrix[0].length;
        int rowSt = 0, colSt = 0, rowEnd = m - 1, colEnd = n - 1;
        while(list.size() < m * n){
            //For starting row addition
            for(int i = colSt; i <= colEnd; i++){
                list.add(matrix[rowSt][i]);
            }

            //To add last colm
            for(int i = rowSt + 1; i <= rowEnd; i++){
                list.add(matrix[i][colEnd]);
            }
            //To add last row
            if(rowSt != rowEnd){
                for(int i = colEnd - 1; i >= colSt; i--){
                    list.add(matrix[rowEnd][i]);
                }
            }
            //To add first colm
            if(colSt != colEnd){
                for(int i = rowEnd - 1; i >= rowSt + 1; i--){
                    list.add(matrix[i][colSt]);
                }
            }
            colSt++;
            colEnd--;
            rowSt++;
            rowEnd--;
        }
        return list;
    }
}

Posted on In

复习

深度优先遍历

递归
以中序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return result;
        inorder(root);
        return result;
    }

    private void inorder(TreeNode node){
        if (node == null) return;
        inorder(node.left);
        result.add(node.val);
        inorder(node.right);
    }
}

迭代
前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }  

        return result;
    }
}

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        Collections.reverse(result);
        return result;
    }
}

统一迭代
以中序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

DFS

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>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        return result;
    }

    private void dfs(TreeNode node, int depth){
        if (node == null) return;
        depth++;

        if (depth > result.size()){
            result.add(new ArrayList<Integer>());
        }

        result.get(depth - 1).add(node.val);

        if (node.left != null) dfs(node.left, depth);
        if (node.right != null) dfs(node.right, depth);
    }
}

广度优先遍历

BFS

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 List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int length = queue.size();
            List<Integer> itemList = new ArrayList<>();
            while(length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(itemList);
        }

        return result;
    }
}

226 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    private void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

101 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }
    private boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right, right.left);

        return compareInside && compareOutside;
    }
}

104 二叉树最大深度

1
2
3
4
5
6
7
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

111 二叉树最小深度

递归

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 mindepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root,0);

        return mindepth;
    }

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (root.left == null && root.right == null){
            if (mindepth > depth){
                mindepth = Math.min(depth, mindepth);
                return;
            }
        }
        
        if (root.left != null){
            dfs(root.left, depth);
        }
        if (root.right != null){
            dfs(root.right, depth);
        }
    }
}

迭代

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 {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            depth++;
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null){
                    return depth;
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

222 完全二叉树节点个数

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

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;

        while (left != null){
            left = left.left;
            leftDepth++;
        }

        while (right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

110 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root){
        if (root == null) return 0;
        int left = getHeight(root.left);
        if (left == -1) return -1;
        int right = getHeight(root.right);
        if (right == -1) return -1;

        if (Math.abs(left - right) > 1){
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

257 二叉树的所有路径

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

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();

        getPaths(root, paths);
        return result;
    }

    private void getPaths(TreeNode root, List<Integer> paths){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));

            result.add(sb.toString());

            return;
        }

        if (root.left != null) {
            getPaths(root.left, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null) {
            getPaths(root.right, paths);

            paths.remove(paths.size() - 1);
        }
    }
}

404 左叶子之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }

        if (root.left != null) sumOfLeftLeaves(root.left);
        if (root.right != null) sumOfLeftLeaves(root.right);
        return sum;
    }
}

513 找树左下角的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            for (int i = 0; i < length; i++){
                TreeNode node = queue.poll();
                if (i == 0){
                    result = node.val;
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int val = 0;
    int maxDepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return val;
        dfs(root, 0);
        return val;
    }

    private void dfs(TreeNode root, int depth){
        depth++;
        if (root.left == null && root.right == null){
            if (depth > maxDepth){
                maxDepth = depth;
                val = root.val;
            }
        }
        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);

    }
}

112 路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;
        if (root.left == null && root.right == null){
            if (targetSum == 0){
                return true;
            }
        }
        boolean left = hasPathSum(root.left, targetSum);
        boolean right = hasPathSum(root.right,targetSum);
        return left || right;
    }
}

113 路径总和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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();
        getPaths(root, paths, targetSum);
        return result;
    }

    private void getPaths(TreeNode node, List<Integer> paths, int targetSum){
        paths.add(node.val);
        targetSum -= node.val;
        if (node.left == null && node.right == null){
            if (targetSum == 0){
                result.add(new ArrayList<Integer>(paths));
            }
        }

        if (node.left != null){
            getPaths(node.left, paths, targetSum);
            paths.remove(paths.size() - 1);
        }

        if (node.right != null){
            getPaths(node.right, paths, targetSum);
            paths.remove(paths.size() - 1);
        }
    }
}

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

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

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS >= inE || postS >= postE) return null;

        int rootVal = postorder[postE - 1];
        int rootIndex = map.get(rootVal);
        int lengthOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lengthOfLeft);
        root.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lengthOfLeft, postE - 1);

        return root;
    }
}

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

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
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;

        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;

        int rootVal = preorder[preS];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(preorder, preS + 1, preS + lenOfLeft + 1, inorder, inS, rootIndex);
        root.right = buildHelper(preorder, preS + lenOfLeft + 1, preE, inorder, rootIndex + 1, inE);
        return root;
    }
}

654 最大二叉树

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
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) return null;
        return constructHelper(nums, 0, nums.length);
    }

    private TreeNode constructHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        
        int[] max = getMaximum(nums, start, end);
        int maxValue = max[0];
        int maxIndex = max[1];

        TreeNode root = new TreeNode(maxValue);
        root.left = constructHelper(nums, start, maxIndex);
        root.right = constructHelper(nums, maxIndex + 1, end);

        return root;

    }

    private int[] getMaximum(int[] nums, int start, int end){
        int maxVal = Integer.MIN_VALUE;
        int index = start;
        for (int i = start; i < end; i++){
            if (nums[i] > maxVal){
                maxVal = nums[i];
                index = i;
            }
        }

        return new int[] {maxVal, index};
    }
}

617 合并二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;

        if (root1 == null && root2 != null) return root2;

        if (root1 != null && root2 == null) return root1;

        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

700 二叉搜索树中的搜索

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val){
            return root;
        } else if (root.val > val){
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

98 验证二叉搜索树

中序递归判断数组

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<Integer> result = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        inorder(root);
        return isInOrder(result);
    }

    private void inorder(TreeNode root){
        if (root == null) return;
        inorder(root.left);
        result.add(root.val);
        inorder(root.right);
    }
    private boolean isInOrder(List<Integer> result){
        for (int i = 1; i < result.size(); i++){
            if (result.get(i - 1) >= result.get(i)) return false;
        }
        return true;
    }
}

记录上一个node 比较root和node的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (!left) return false;

        if (max != null && root.val <= max.val) return false;
        max = root;

        boolean right = isValidBST(root.right);
        return right;
    }
}

107 二叉树的层次遍历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

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            List<Integer> item = new ArrayList<>();
            while(length-- > 0){
                TreeNode node = queue.poll();
                item.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(item);
        }

        Collections.reverse(result);

        return result;
    }
}

199 二叉树的右视图

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
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (length == 0){
                    result.add(node.val);
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return result;
    }
}

530 二叉搜索树的最小绝对差

利用中序遍历二叉搜索树，比较当前值和之前的值的差值

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 {
    List<Integer> result = new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        inorder(root);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < result.size(); i++){
            int diff = result.get(i) - result.get(i -1);
            if (diff < min) {
                min = diff;
            }
        }

        return min;
    }

    private void inorder(TreeNode node){
        if (node == null) return;

        inorder(node.left);
        result.add(node.val);
        inorder(node.right);
    }
}

在中序遍历之中记录一个pre node 之后再记录min的差值，进行比较，二叉搜索树特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        getMinimumDifference(root.left);
        
        if (pre != null && Math.abs(pre.val - root.val) < min) min = Math.abs(pre.val - root.val);
        pre = root;
        getMinimumDifference(root.right);

        return min;
    }
}

501 二叉搜索树中的众数

利用map 前序遍历计数，然后再统计出现频率最多的数字
需要背语法

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

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    List<Integer> result = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        preorder(root);
        List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
				.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
				.collect(Collectors.toList());
        result.add(mapList.get(0).getKey());
        for (int i = 1; i < mapList.size(); i++) {
			if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
				result.add(mapList.get(i).getKey());
			} else {
				break;
			}
		}
		return result.stream().mapToInt(Integer::intValue).toArray();
    }

    private void preorder(TreeNode root){
        if (root == null) return;
        if (map.containsKey(root.val)){
            map.put(root.val, map.get(root.val) + 1);
        } else {
            map.put(root.val, 1);
        }

        preorder(root.left);
        preorder(root.right);
    }
}

一次中序遍历利用二叉搜索树特性
记录prenode后，记录count， 比较maxcount，等于添加到数组中，大于就清空原来的数组，再添加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
class Solution {
    List<Integer> result = new ArrayList<>();
    int maxCount = 0;
    int count = 0;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void inorder(TreeNode root){
        if (root == null) return;

        inorder(root.left);
        if (pre == null){
            count = 1;
        } else if (pre.val == root.val){
            count++;
        } else {
            count = 1;
        }

        pre = root;

        if (count > maxCount){
            result.clear();
            result.add(root.val);
            maxCount = count;
        } else if (count == maxCount){
            result.add(root.val);
        }

        inorder(root.right);
    }
}

迭代法同理，在处理node时同样的逻辑

236 二叉树的最近公共祖先

此题是自底向上查找，就是回溯
在二叉树中 后序遍历就是自底向上

如果有一个节点，发现左子树出现节点P，右子树出现节点q，或者相反，那么该节点就是公共祖先

如果遇到p 返回p如果遇到q返回q，如果左右子树不为空，中节点就是最近祖先
整体过程如图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 root;

        if (left == null && right != null) return right;
        else if (left != null && right == null) return left;
        else return null;
        
    }
}

Posted on In

复习

深度优先遍历
迭代
前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return result;
    }
}

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        Collections.reverse(result);

        return result;
    }
}

统一迭代法
前序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

递归
前序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return result;
    }
    public void preorder(TreeNode node){
        if (node == null) return;
        result.add(node.val);
        preorder(node.left);
        preorder(node.right);
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        return result;
    }
    public void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (result.size() < depth){
            result.add(new ArrayList<Integer>());
        }

        result.get(depth - 1).add(root.val);

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

广度优先遍历
BFS

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
class Solution {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int length = queue.size();
            List<Integer> itemList = new ArrayList<>();
            while (length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(itemList);
        }

        return result;
    }
}

226 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    private void swapChildren(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

101 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;

        return compare(root.left, root.right);
    }

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

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right, right.left);

        return compareInside && compareOutside;
    }
}

104 二叉树最大深度

1
2
3
4
5
6
7
8

class Solution {
    public int maxDepth(TreeNode root) {

        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

111 二叉树最小深度

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 0);
        return minDepth;

    }
    private void dfs(TreeNode node, int depth){
        if (node == null) return;
        depth++;
        if (node.left == null && node.right == null){
            if (depth < minDepth){
                minDepth = depth;
            }
        }

        if (node.left != null) dfs(node.left, depth);
        if (node.right != null) dfs(node.right, depth);
    }
}

层序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            depth++;
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null){
                    return depth;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

222 完全二叉树节点个数

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
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = 0;
        int rightDepth = 0;

        while (left != null){
            left = left.left;
            leftDepth++;
        }
        while (right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

110 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node){
        if (node == null) return 0;
        int left = getHeight(node.left);
        if (left == -1) return -1;
        int right = getHeight(node.right);
        if (right == -1) return -1;

        if (Math.abs(left - right) > 1){
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

257 二叉树的所有路径

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
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;

        List<Integer> paths = new ArrayList<>();

        getPaths(root, paths);

        return result;
    }

    private void getPaths(TreeNode node, List<Integer> paths){
        paths.add(node.val);

        if (node.left == null && node.right == null){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            result.add(sb.toString());
            return;
        }

        if (node.left != null) {
            getPaths(node.left, paths);
            paths.remove(paths.size() - 1);
        }

        if (node.right != null) {
            getPaths(node.right, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

404 左叶子之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return sum;
        getSums(root, 0);

        return sum;
    }

    private void getSums(TreeNode node, int depth){
        if (node == null) return;
        depth++;

        if (node.left != null && node.left.left == null && node.left.right == null){
            sum += node.left.val;
        }
        if (node.left != null) getSums(node.left, depth);
        if (node.right != null) getSums(node.right, depth);
    }
}

513 找树左下角的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int result = root.val;
        while (!queue.isEmpty()){
            int length = queue.size();
            for (int i = 0; i < length; i++){
                TreeNode node = queue.poll();
                if (i == 0){
                    result = node.val;
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return result;
    }
}

112 路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0) return true;
        }

        boolean left = hasPathSum(root.left, targetSum);
        boolean right = hasPathSum(root.right, targetSum);

        return left || right;
    }
}

113 路径总和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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();
        getPaths(root, paths, targetSum);
        return result;
    }

    private void getPaths(TreeNode node, List<Integer> paths, int targetSum){
        paths.add(node.val);
        targetSum -= node.val;
        if (node.left == null && node.right == null){
            if (targetSum == 0){
                result.add(new ArrayList<Integer>(paths));
                return;
            }
        }

        if (node.left != null) {
            getPaths(node.left, paths, targetSum);
            paths.remove(paths.size() - 1);
        }

        if (node.right != null) {
            getPaths(node.right, paths, targetSum);
            paths.remove(paths.size() - 1);
        }
    }
}

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

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
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;

        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS >= inE || postS >= postE) return null;

        int rootVal = postorder[postE - 1];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        root.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lenOfLeft);
        root.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lenOfLeft, postE - 1);

        return root;
    }
}

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

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
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;

        int rootVal = preorder[preS];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(preorder, preS + 1, preS + 1 + lenOfLeft, inorder, inS, rootIndex);
        root.right = buildHelper(preorder, preS + 1 + lenOfLeft, preE, inorder, rootIndex + 1, inE);

        return root;

    }
}


654 最大二叉树

构造树采用前序遍历

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 TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length);
    }

    private TreeNode traversal(int[] nums, int start, int end){
        if (start >= end) return null;
        int maxValue = Integer.MIN_VALUE;
        int maxIndex = start;
        for (int i = start; i < end; i++){
            if (nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }

        TreeNode root = new TreeNode(maxValue);

        root.left = traversal(nums, start, maxIndex);
        root.right = traversal(nums, maxIndex + 1, end);
        return root;
    }
}

617 合并二叉树

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;

        if (root1 == null && root2 != null){
            return root2;
        }  
        if (root1 != null && root2 == null){
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        
        return root;
    }
}

700 二叉搜索树中的搜索

二叉树递归 利用特性

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;

        if (root.val < val) return searchBST(root.right, val);
        if (root.val > val) return searchBST(root.left, val);

        return root;
    }
}

二叉树特性的迭代
不需要栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        while (root != null){
            if (val < root.val){
                root = root.left;
            } else if (val > root.val){
                root = root.right;
            } else {
                return root;
            }
        }

        return root;
    }
}

98 验证二叉搜索树

统一迭代，用一个pre Node记录上一个node进行比较

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 {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return false;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                TreeNode temp = stack.pop();
                if (pre != null && pre.val >= temp.val){
                    return false;
                }

                pre = temp;
            }
        }
        return true;
    }
}

递归(中序遍历) 需要强化记忆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean left = isValidBST(root.left);
        if (!left) return false;
        if (max != null && root.val <= max.val){
            return false;
        }
        max = root;

        boolean right = isValidBST(root.right);
        return right;
    }
}

Posted on In

复习

深度优先遍历

前中后序遍历

递归

前序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return result;
    }

    public void preorder(TreeNode node){
        if (node == null) return;

        result.add(node.val);
        preorder(node.left);
        preorder(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
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                stack.push(node);
                stack.push(null);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

不同迭代

前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return result;
    }
}

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        Collections.reverse(result);
        return result;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    public void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (result.size() < depth){
            result.add(new ArrayList<Integer>());
        }

        result.get(depth - 1).add(root.val);
        
        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
        
    }
}

广度优先遍历

BFS

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 {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            
            int length = queue.size();
            List<Integer> itemList = new ArrayList<>();

            while (length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(itemList);
        }

        return result;
    } 
}

翻转二叉树

前序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

迭代

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 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            swapChildren(node);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

对称二叉树、

前序
递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right, right.left);

        return compareInside && compareOutside;
    }
}

迭代

利用队列

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 isSymmetric(TreeNode root) {
        if (root == null) return false;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }
}

二叉树最大深度

递归
后序 高度
前序 深度

此题求根节点高度

1
2
3
4
5
6
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

迭代层序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.offer(root);

        while (!queue.isEmpty()){
            int length = queue.size();
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }

        return depth;
    }
}

二叉树最小深度

迭代 层序遍历，遇到叶子结点直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int length = queue.size();
            depth++;
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

DFS
慢是因为会遍历所有结点，但层序遍历不会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 0);
        return minDepth;
    }

    public void dfs(TreeNode root, int depth){
        if (root == null) return;

        depth++;
        if (root.left == null && root.right == null){
            minDepth = Math.min(depth, minDepth);
            return;
        }
        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

完全二叉树的结点个数

递归

1
2
3
4
5
6
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.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
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;

        while(left != null){
            left = left.left;
            leftDepth++;
        }

        while (right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

平衡二叉树

高度 后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode node){
        if (node == null) return 0;

        int leftHeight = getHeight(node.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node.right);
        if (rightHeight == -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

二叉树所有路径

前序遍历找路径

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 {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();
        getPaths(root, paths);
        return result;
    }
    private void getPaths(TreeNode root, List<Integer> paths){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            result.add(sb.toString());
            return; 
        }

        if (root.left != null) {
            getPaths(root.left, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null) {
            getPaths(root.right, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

左叶子之和

前序遍历，递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return sum;

        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }

        if (root.left != null) sumOfLeftLeaves(root.left);
        if (root.right != null) sumOfLeftLeaves(root.right);
        return sum;
    }
}

找树左下角的值

层序遍历

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

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;

        int result = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int length = queue.size();

            for (int i = 0; i < length; i++){
                TreeNode node = queue.poll();
                if (i == 0){
                    result = node.val;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return result;
    }
}

dfs 递归记录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
class Solution {
    int maxDepth = 0;
    int result = 0;

    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return result;
        getValue(root, 0);
        
        return result;    
    }

    public void getValue(TreeNode root, int depth){
        if (root == null) return;
        depth++;

        if (root.left == null && root.right == null){
            if (maxDepth < depth){
                maxDepth = depth;
                result = root.val;
            }
        }

        if (root.left != null) getValue(root.left, depth);
        if (root.right != null) getValue(root.right, depth);
    }
}

路径总和

递归求和

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

        targetSum -= root.val;
        if (root.left == null && root.right == null){
            if (targetSum == 0) return true;
        }
        boolean left = false;
        boolean right = false;
        if (root.left != null){
            left = hasPathSum(root.left, targetSum);
        }
        if (root.right != null) {
            right = hasPathSum(root.right, targetSum);
        }
        return left || right;
    }
}

路径总和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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;

        List<Integer> paths = new ArrayList<>();

        getPaths(root, targetSum, paths);

        return result;
    }

    public void getPaths(TreeNode root, int targetSum, List<Integer> paths){
        paths.add(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null){
            if (targetSum == 0){
                result.add(new ArrayList<Integer>(paths));
                return;
            }
        }

        if (root.left != null){
            getPaths(root.left, targetSum, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null){
            getPaths(root.right, targetSum, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

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

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 {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;

        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS >= inE || postS >= postE) return null;

        int rootVal = postorder[postE - 1];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        root.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lenOfLeft);
        root.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lenOfLeft, postE - 1);

        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
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;

        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;

        int rootVal = preorder[preS];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex = map.get(rootVal);
        int lenOfLeft = middleIndex - inS;

        root.left = buildHelper(preorder, preS + 1, preS + lenOfLeft + 1, inorder, inS, middleIndex);
        root.right = buildHelper(preorder, preS + lenOfLeft + 1, preE, inorder, middleIndex + 1, inE);
        return root;
    }
}

Posted on In

复习

前中后序递归

以前序为例

前序： 中左右
中序： 左中右
后序： 左右中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    List<Integer> result = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return result;
    }

    public void preorder(TreeNode root){
        if (root == null) return;
        result.add(root.val);
        preorder(root.left);
        preorder(root.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
class Solution {
    List<Integer> result = new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();

            if (node != null){
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

前序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return result;
    }
}

中序迭代

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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        Collections.reverse(result);
        return result;
    }
}

DFS 层序打出数个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 0);

        return result;
    }

    public void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (result.size() < depth){
            result.add(new ArrayList<Integer>());
        }
        result.get(depth - 1).add(root.val);

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

BFS 层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new ArrayDeque<>();    
        queue.add(root);
        while (!queue.isEmpty()){
            int length = queue.size();
            List<Integer> itemList = new ArrayList<>();

            while (length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(itemList);
        }

        return result;
    }
}

翻转二叉树

前序和后序都可，中序不可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

前序统一迭代法

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
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if(node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            } else {
                swapChildren(stack.pop());
            }
        }

        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

层序迭代

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
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int length = queue.size();
            while (length-- > 0){
                TreeNode node = queue.poll();
                swapChildren(node);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

对称二叉树

注意对比过程和递归过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }
}

迭代法

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

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
        
    }
}

二叉树最大深度

此为后序遍历 递归

1
2
3
4
5
6
7
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

前序递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int depth = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        getDepth(root, 0);
        return depth;
    }
    public void getDepth(TreeNode node, int deep){
        if (node == null) return;
        deep++;
        depth = Math.max(deep,depth);
        if (node.left != null) getDepth(node.left, deep);
        if (node.right != null) getDepth(node.right, deep);
    }
}

层序遍历迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue= new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            depth++;
            int length = queue.size();
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

二叉树的最小深度

前序求深度，后序求高度

层序遍历到第一个叶子结点的层数

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 {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            depth++;
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null){
                    return depth;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        return getDepth(root);
    }

    public int getDepth(TreeNode root){
        if (root == null) return 0;
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);

        if (root.left == null && root.right != null) return 1 + rightDepth;
        if (root.left != null && root.right == null) return 1 + leftDepth;

        int result = 1 + Math.min(leftDepth, rightDepth);

        return result;
    }
}

完全二叉树的节点个数

递归， 后序递归

1
2
3
4
5
6
7
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

层级遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            sum += length;
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return sum;
    }
}

完全二叉树性质

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

        TreeNode left = root.left;
        TreeNode right = root.right;
        
        int leftDepth = 0;
        int rightDepth = 0;

        while (left != null){
            left = left.left;
            leftDepth++;
        }   

        while (right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

平衡二叉树

因为要求高度，则需要后序遍历
递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode node){
        if (node == null) return 0;
        int leftHeight = getHeight(node.left);

        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node.right);

        if (rightHeight == -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

二叉树的所有路径

要测路径就要用前序遍历

递归

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

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> paths = new ArrayList<>();
        getPaths(root, result, paths);
        return result;
    }
    public void getPaths(TreeNode root, List<String> result, List<Integer> paths){
        paths.add(root.val);

        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            result.add(sb.toString());
            return;
        }

        if (root.left != null) {
            getPaths(root.left, result, paths);
            paths.remove(paths.size() - 1);
        }

        if (root.right != null){
            getPaths(root.right, result, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

左叶子之和

需要通过父节点查看左叶子结点是不是叶子结点
前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        } 

        if (root.left != null) sumOfLeftLeaves(root.left);
        if (root.right != null) sumOfLeftLeaves(root.right);
        return sum;
    }
}

后序遍历迭代

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

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        int sum = 0;
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();

            if (node.left != null){
                if (node.left.left == null && node.left.right == null){
                    sum += node.left.val;
                }
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }

        return sum;
    }
}

513 找树左下角的值

层序遍历经典题目

迭代法
更新最左边的值指到遍历所有层，获得结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int length = queue.size();
            for (int i = 0; i < length; i++){
                TreeNode node = queue.poll();
                if (i == 0) result = node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

DFS模版

注意判断最大depth的值和更新result的值

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
class Solution {

    int result = 0;
    int maxDepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        traversal(root, 0);
        return result;
    }

    public void traversal(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (root.left == null && root.right == null){
            if (depth > maxDepth){
                maxDepth = depth;
                result = root.val;
            }
        }

        if (root.left != null) traversal(root.left, depth);
        if (root.right != null) traversal(root.right, depth);
    }

}

路径总和

自己写的办法，利用找path的迭代方法，找出总和等不等于的方法

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
class Solution {
    boolean hasPath = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return hasPath;
        List<Integer> paths = new ArrayList<>();
        getPathSum(root, paths, targetSum);

        return hasPath;
    }

    public void getPathSum(TreeNode node, List<Integer> paths, int targetSum){
        paths.add(node.val);
        if (node.left == null && node.right == null){
            int sum = 0;
            for (int i : paths){
                sum += i;
            }

            if (sum == targetSum){
                hasPath = true;
                return;
            }
        }

        if (node.left != null) {
            getPathSum(node.left, paths, targetSum);
            paths.remove(paths.size() - 1);
        }

        if (node.right != null) {
            getPathSum(node.right, paths, targetSum);
            paths.remove(paths.size() - 1);
        }
    }
}

不需要确定path的方法，只需要计算等不等于targetsum

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;

        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0) return true;
        }

        if (root.left != null){
            boolean left = hasPathSum(root.left, targetSum);
            if (left) return true;
        }

        if (root.right != null){
            boolean right = hasPathSum(root.right, targetSum);
            if (right) return true;
        }

        return false;
    }
}

迭代法先跳过
利用前序遍历，先推中间，再右，再左
用两个stack，一个记录node，一个记录sum值，找到就返回true

113 路径之和II

自己写的办法，利用找path的迭代方法，并能打印出path

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

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();

        getPaths(root, paths, targetSum);

        return result;
    }
    public void getPaths(TreeNode root, List<Integer> paths, int targetSum){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            int sum = 0;
            for (int i : paths){
                
                sum += i;
            }

            if (sum == targetSum){
                result.add(new ArrayList<>(paths));
            }
            return;
        }

        if (root.left != null){
            getPaths(root.left, paths, targetSum);
            paths.remove(paths.size() - 1);
            
        }
        if (root.right != null){
            getPaths(root.right, paths, targetSum);
            paths.remove(paths.size() - 1);
        }
    }

}

优化，不用for loop判断targetsum
利用递归参与到判断targetSum中

targetSum - root.val;
每次都减去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
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();

        getPaths(root, paths, targetSum);

        return result;
    }
    public void getPaths(TreeNode root, List<Integer> paths, int targetSum){
        paths.add(root.val);
        if (root.left == null && root.right == null){

            if (targetSum - root.val == 0){
                result.add(new ArrayList<>(paths));
            }
            return;
        }

        if (root.left != null){
            getPaths(root.left, paths, targetSum-root.val);
            paths.remove(paths.size() - 1);
            
        }
        if (root.right != null){
            getPaths(root.right, paths, targetSum-root.val);
            paths.remove(paths.size() - 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
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0 || inorder.length == 0){
            return null;
        }

        return buildHelper(inorder, 0 , inorder.length, postorder, 0, postorder.length);
    }

    public TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
        if (postStart == postEnd){
            return null;
        }

        int rootVal = postorder[postEnd - 1];
        TreeNode node = new TreeNode(rootVal);

        int middleIndex;
        for (middleIndex = 0; middleIndex < inEnd; middleIndex++){
            if (inorder[middleIndex] == rootVal) break;
        }

        int leftInStart = inStart;
        int leftInEnd = middleIndex;
        int rightInStart = middleIndex + 1;
        int rightInEnd = inEnd;

        int leftPostStart = postStart;
        int leftPostEnd = postStart + (middleIndex - inStart);
        int rightPostStart = leftPostEnd;
        int rightPostEnd = postEnd - 1;

        node.left = buildHelper(inorder, leftInStart, leftInEnd, postorder, leftPostStart, leftPostEnd); 
        node.right = buildHelper(inorder, rightInStart, rightInEnd, postorder, rightPostStart, rightPostEnd); 

        return node;
    }
}

利用map查找index 更省时间

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 {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS == inE || postS == postE) return null;
        int rootValue = postorder[postE - 1];
        TreeNode node = new TreeNode(rootValue);
        int rootIndex = map.get(rootValue);
        int lenOfLeft = rootIndex - inS;
        node.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lenOfLeft);
        node.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lenOfLeft, postE - 1);
        return node;
    }
}

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

通过递归注意边界
通过map查找更快

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

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;

        int rootVal = preorder[preS];
        TreeNode root = new TreeNode(rootVal);
        int midIndex = map.get(rootVal);
        int lenOfLeft = midIndex - inS;

        root.left = buildHelper(preorder, preS + 1, preS + lenOfLeft + 1, inorder, inS, midIndex);
        root.right = buildHelper(preorder, preS + lenOfLeft + 1, preE, inorder, midIndex + 1, inE);
        return root;
    }
}

Posted on In

复习

深度优先遍历

前序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result){
        if (root == null) return;

        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return result;
    }
}

统一迭代

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
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);

                stack.push(node);
                stack.push(null);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

中序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        inorder(root, result);

        return result;
    }
    public void inorder(TreeNode root, List<Integer> result){
        if (root == null) return;
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

迭代

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 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

统一迭代

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

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();

            if (node != null){
                if (node.right != null) stack.push(node.right);

                stack.push(node);
                stack.push(null);

                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

后序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        postorder(root, result);

        return result;
    }

    public void postorder(TreeNode root, List<Integer> result){
        if (root == null) return;

        postorder(root.left, result);
        postorder(root.right, result);

        result.add(root.val);
    }
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(result);
        
        return result;
    }
}

统一迭代

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
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                stack.push(node);
                stack.push(null);

                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

广度优先遍历

DFS

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        dfs(root, 0, result);

        return result;
    }

    public void dfs(TreeNode root, int depth, List<List<Integer>> result){
        if (root == null) return;

        depth++;

        if (result.size() < depth){
            List<Integer> itemList = new ArrayList<>();
            result.add(itemList);
        }

        result.get(depth - 1).add(root.val);
        dfs(root.left, depth, result);
        dfs(root.right, depth, result);
    }
}

BFS

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int length = queue.size();

            while (length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right); 
            }
            result.add(itemList);
        }

        return result;
    }
}

翻转二叉树

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    public void swapChildren(TreeNode root){
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
    }
}

迭代法

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

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();

            swapChildren(node);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        return root;

    }

    public void swapChildren(TreeNode root){
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
    }
}

对称二叉树

递归法

在判断左右节点的值时，不能依据两个node是否为null，那样会破坏递归，直接返回值
只能判断两个值是否相等，然后继续递归到最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if (left == null && right != null) return false;
        if (left != null && right == null) return false;
        if (left == null && right == null) return true;
        if (left.val != right.val) return false;

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right, right.left);

        return compareOutside && compareInside;
    }
}

迭代法

建立队列时用linkedlist， ArrayDeque不接受null

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 {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            if (left == null && right == null) continue;

            if (left == null || right == null || left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }
}

二叉树最大深度

递归法

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        int depth = 1 + Math.max(left, right);
        return depth;
    }
}

前序遍历
注意在class里面设置depth的值，进行调整，即设置环境变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int depth = 0;
    public int maxDepth(TreeNode root) {
        dfs(root, 0);
        return depth;
    }

    public void dfs(TreeNode root, int curDepth){
        if (root == null) return;

        curDepth++;
        depth = Math.max(curDepth, depth);
        dfs(root.left,curDepth);
        dfs(root.right,curDepth);
    }
}


层序遍历迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            while (length-- > 0){
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            
            depth++;
        }

        return depth;
    }
}

二叉树最小深度

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        if (root.left == null){
            return 1 + right;
        }
        if (root.right == null){
            return 1 + left;
        }

        return Math.min(left, 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
class Solution {
    int depth = 0;
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        
        getDepth(root);

        return minDepth == Integer.MAX_VALUE ? 0 : minDepth;
    }

    public void getDepth(TreeNode root){
        if (root == null) return;
        depth++;
        getDepth(root.left);
        getDepth(root.right);

        if (root.left == null && root.right== null) {
            minDepth = Math.min(minDepth, depth);
        }
        depth--;
    }

    
}

完全二叉树的节点数

后序遍历

1
2
3
4
5
6
7
8

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

前序遍历 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    int count = 0;
    public int countNodes(TreeNode root) {
        dfs(root);
        return count;
    }

    public void dfs(TreeNode root){
        if (root == null) return;
        count++;

        if (root.left != null) dfs(root.left);
        if (root.right != null) dfs(root.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

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = 0;
        int rightDepth = 0;

        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;

        while (leftNode != null){
            leftNode = leftNode.left;
            leftDepth++;
        }

        while (rightNode != null){
            rightNode = rightNode.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

110 平衡二叉树

https://leetcode.com/problems/balanced-binary-tree/

判断一个二叉树每个节点左右两个子树的高度差绝对值不超过一

求高度 用后序遍历
求深度 用前序遍历

在用后序遍历时 求左子树和右子树的高度差值，如果差值小于等于1，返回当前二叉树高度，否则-1；
返回当前节点为根节点的树的最大高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root){
        if (root == null) return 0;

        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }

        return Math.max(leftHeight, rightHeight) + 1;
    }
}


257 二叉树的所有路径

https://leetcode.com/problems/binary-tree-paths/description/

返回从根节点到叶子节点所有路径 需要前序遍历

此题难点是回溯
在前序遍历之中，进行回溯
在前序遍历添加到result数组之后返回

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
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();

        if (root == null) return result;

        List<Integer> paths = new ArrayList<>();

        traversal(root, result, paths);

        return result;
    }

    public void traversal(TreeNode root, List<String> result, List<Integer> paths){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            
            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            result.add(sb.toString());
        }

        if (root.left != null){
            traversal(root.left, result, paths);
            paths.remove(paths.get(paths.size() - 1));
        }

        if (root.right != null){
            traversal(root.right, result, paths);
            paths.remove(paths.get(paths.size() - 1));
        }
    }
}

迭代法
把路径和node一起推入栈中，node节点为叶子结点时，添加result，否则，就把下一个path写进stack中

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

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;

        Stack<Object> stack = new Stack<>();
        stack.push(root);
        stack.push(root.val + "");

        while (!stack.isEmpty()){
            String path = (String) stack.pop();
            TreeNode node = (TreeNode) stack.pop();

            if (node.left == null && node.right == null){
                result.add(path);
            }

            if (node.right != null) {
                stack.push(node.right);
                stack.push(path + "->" + node.right.val);
            }

            if (node.left != null){
                stack.push(node.left);
                stack.push(path + "->" + node.left.val);
            }
        }

        return result;
    }
}

404 左叶子之和

计算给定二叉树的所有左叶子之和
判断左叶子的方法，就是该节点的左节点不为空，该节点的左节点的左节点和左节点的右节点为空，则该节点的左节点为左叶子结点

递归法 通过后序遍历完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 0;
        int leftSum = sumOfLeftLeaves(root.left);
        int rightSum = sumOfLeftLeaves(root.right);

        int midValue = 0;

        if (root.left != null && root.left.left == null && root.left.right == null){
            midValue = root.left.val;
        }

        return leftSum + rightSum + midValue;
    }
}

迭代法

一个前序迭代，就可以完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) stack.push(root);
        if (root == null) return 0;
        int sum = 0;
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.left != null && node.left.left == null && node.left.right == null){
                sum += node.left.val;
            }
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return sum;

    }
}

Posted on In

复习

深度优先遍历

前序遍历

https://leetcode.com/problems/binary-tree-preorder-traversal/description/

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        preorder(root, result);

        return result;
    }

    public void preorder(TreeNode root, List<Integer> result){
        if (root == null) return;

        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }

        return result;
    }
}

统一迭代法

node设置的时候，要注意弹出之后的下一个值才是重点

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
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.peek();
            if (node != null){
                stack.pop();
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
            } else {
                stack.pop();
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

后序遍历

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        postorder(root, result);

        return result;
    }

    public void postorder(TreeNode root, List<Integer> result){
        if (root == null) return;
        postorder(root.left, result);
        postorder(root.right, result);
        result.add(root.val);
    }
}

####迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();

            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }

        Collections.reverse(result);

        return result;
    }
}

####统一迭代法

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

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                stack.push(node);
                stack.push(null);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

中序遍历

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        inorder(root, result);

        return result;
    }

    public void inorder(TreeNode root, List<Integer> result){
        if (root == null) return;

        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

迭代法

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

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
				cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
}

统一迭代法

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

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if (node.right != null) stack.push(node.right);
                stack.push(node);
                stack.push(null);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }

        return result;
    }
}

广度优先遍历 层序遍历

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

DFS

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

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    public void dfs(TreeNode root, int depth, List<List<Integer>> result){
        if (root == null) return;

        depth++;

        if (result.size() < depth){
            List<Integer> itemList = new ArrayList<>();
            result.add(itemList);
        }

        result.get(depth - 1).add(root.val);

        dfs(root.left, depth, result);
        dfs(root.right, depth, result);
    }
}

BFS

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        bfs(root, result);

        return result;
    }

    public void bfs(TreeNode root, List<List<Integer>> result){
        if (root == null) return;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int length = queue.size();
            while (length-- > 0){
                TreeNode node = queue.poll();
                itemList.add(node.val);
                if (node.left != null ) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            result.add(itemList);
        }
    }
}

104 二叉树的最大深度

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

二叉树的深度，指根节点到该节点的最长简单路径边的条数或者节点数
二叉树的高度，指该节点到叶子结点的最长简单路径边的条数或者节点数

而根节点的高度就是二叉树的最大深度

使用前序遍历求的是深度，使用后序遍历求的是高度
此题可通过后序遍历求根节点的高度

depth 每次递归更新加一和最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int maxDepth(TreeNode root) {
        return getDepth(root);
    }
    public int getDepth(TreeNode root){
        if (root == null) return 0;

        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        int depth = 1 + Math.max(leftDepth, rightDepth);

        return depth;
    }
}

精简

1
2
3
4
5
6
class Solution {
	public int maxDepth(TreeNode root){
		if (root == null) return 0;
		return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
}

迭代法可通过层序遍历bfs拿到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

class Solution {
    public int maxDepth(TreeNode root) {
        return bfs(root);
    }

    public int bfs(TreeNode root){
        if (root == null) return 0;
        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int length = queue.size();

            while (length-- > 0){

                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            depth++;
        }

        return depth;
    }
}

559 n叉树的最大深度

层序遍历

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

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;

        Queue<Node> queue = new ArrayDeque<>();

        int depth = 0;
        queue.add(root);
        while (!queue.isEmpty()){
            int length = queue.size();

            while (length-- > 0){
                Node node = queue.poll();
                if (!node.children.isEmpty()){
                    for (Node i : node.children){
                        queue.add(i);
                    }
                }
            }
            depth++;
        }
        return depth;
    }
}

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxDepth(Node root) {
        return getDepth(root);
    }

    public int getDepth(Node root){
        if (root == null) return 0;
        int depth = 0;
        if (!root.children.isEmpty()){
            for (Node i : root.children){
                depth = Math.max(getDepth(i), depth);
            }
        }
        return depth + 1;
    }
}

111 二叉树的最小深度

层序遍历

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

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()){
            depth++;
            int length = queue.size();
            while (length-- > 0){
                TreeNode node = queue.poll();

                if (node.left == null && node.right == null){
                    return depth;
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }

        return depth;
    }
}

递归法
要确定左子树和右子树的情况
和最大深度不同，最大深度，max可以不考虑左子树和右子树的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = minDepth(root.left);

        int rightDepth = minDepth(root.right);

        if (root.left == null && root.right != null){
            return 1 + rightDepth;
        }

        if (root.left != null && root.right == null){
            return 1 + leftDepth;
        }

        int depth = 1 + Math.min(leftDepth, rightDepth);
        return depth;
    } 
}

222 完全二叉树的节点个数

普通二叉树数节点数量

利用后序遍历递归，求数量

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        int num = leftNum + rightNum + 1;

        return num;
    }
}

利用层序遍历统计数量

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

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new ArrayDeque<>();

        queue.add(root);
        int sum = 0;
        while (!queue.isEmpty()){
            int length = queue.size();
            sum += length;

            while (length-- > 0){
                TreeNode node = queue.poll();

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }

        return sum;
    }
}

利用完全二叉树的特性

因为除了最底层没填满外，其他的结点都是满的

如果向左递归的深度，不等于向右递归的深度，则说明不是满二叉树
满二叉树节点为2^depth - 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

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;

        TreeNode right = root.right;

        int leftDepth = 0;
        int rightDepth = 0;

        while (left != null){
            left = left.left;
            leftDepth++;
        }
        while (right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}

复习： 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

复习： 对称二叉树

递归

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 isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {

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

        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        // 比较外侧
        boolean compareOutside = compare(left.left, right.right);
        // 比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }
0%