代码随想录第十六天

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