代码随想录第十八天

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;
    }
}