代码随想录第十五天

Posted on In

复习

依次复习了，前中后序遍历的递归法，迭代法和统一迭代法
统一迭代法有一个简化写法, 以中序遍历为例

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

层序遍历

102 二叉树的层序遍历

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

二叉树的层序遍历迭代法即BFS， 广度优先遍历

利用队列进行广度优先遍历
模拟过程
把root推入队列之中，拿出root之后，把数加入list里面，再把root的左边和右边分别推入队列，在之后，以queue的长度作为loop的依据，依次建立数组并加入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
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 len = queue.size();
			
			while (len-- > 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);
		}
	}
}

DFS， 递归法深度优先遍历

递归法的DFS
利用深度成为索引
模拟过程
deep从0开始，把deep自加一之后，在result里面添加itemlist，再把val加入result的deep-1的list里面，之后重复左边和右边，这样在deep够深的情况是先找到深度优先，在依deep的值的大小加入相对应的list中

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<>();
		dfs(root, 0, result);
		
		return result;
    }
	
	public void dfs(TreeNode node, int depth, List<List<Integer>> result){
		if (node == null) return;
		depth++;
		
		if (result.size() < depth){
			List<Integer> itemList = new ArrayList<>();
			
			result.add(itemList);
		}
		result.get(depth - 1).add(node.val);
		if (node.left != null) dfs(node.left, depth, result);
		if (node.right != null) dfs(node.right, depth, result);
	}
}

107 二叉树的层序遍历II

在层序遍历的基础之上，反转结果

199 二叉树的右视图

在层序遍历的基础之上，查看是否遍历到单层最后面的元素

BFS

在判断BFS的queue的length时，不把所有的值都输入itemlist里面，只需要在length为0时的node的值输入到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> rightSideView(TreeNode root){
		List<Integer> result = new ArrayList<>();
		List<List<Integer>> levelTraversal = bfs(root);
		return result;
	}
	
	public List<List<Integer>> bfs(TreeNode root){
		List<List<Integer>> result = new ArrayList<>();
		if (root == null){
			return result;
		}
		
		Queue<TreeNode> queue = new ArrayDeque<>();
		
		queue.add(root);
		
		while (!queue.isEmpty()){
		
		}
	}
}

DFS

先写出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
26
27
28
29
30
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        dfs(root, 0, result);
        List<Integer> resList = new ArrayList<>();
        for (int i = 0; i < result.size(); i++){
            List<Integer> item = result.get(i);
            resList.add(item.get(item.size() - 1));
        }

        return resList;
    }

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

            result.add(itemList);
        }

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

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

637 二叉树的层平均值

DFS或者BFS之后，计算每个itemList之中的average输出出来

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
30
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {

        List<Double> result = bfs(root);
        return result;
    }

    public List<Double> bfs(TreeNode root){
        List<Double> result = new ArrayList<>();
        if (root == null) return result;

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

            result.add((double) sum / length);
        }

        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
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        dfs(root, 0, result);

        List<Double> resList = new ArrayList<>();

        for (int i = 0; i < result.size(); i++){
            List<Integer> item = result.get(i);
            long sum = 0;
            for (int j : item){
                sum += j;
            }
            resList.add((double) sum / item.size());
        }

        return resList;
    }

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

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

429 N叉树树的层序遍历

BFS

遍历过程中不判断左右，而是将child都输入到queue里面

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

        bfs(root, result);

        return result;
    }

    public void bfs(Node root, List<List<Integer>> result){
        if (root == null) return;
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);

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

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

                if (node.children != null) {
                    for (Node i : node.children){
                        queue.add(i);
                    }
                }
            }
            result.add(itemList);
        }
    }
}

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
26
27

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    public void dfs(Node 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);

        if (root.children != null){
            for (Node i : root.children){
                dfs(i,depth,result);
            }
        }
    }
}

515 在每个树的行中找最大值

BFS或者DFS 输出的list中找到最大值

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

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

        while (!queue.isEmpty()){
            int length = queue.size();
            int max = Integer.MIN_VALUE;
            while (length-- > 0){
                TreeNode node = queue.poll();
                max = Math.max(max, node.val);

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

DFS

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

        dfs(root, 0, result);
        return result;
    }

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

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

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

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

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);

        while (!queue.isEmpty()){
            int length = queue.size();
            Node cur = queue.poll();
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
            
            for (int i = 1; i < length; i++){
                Node next = queue.poll();
                if (next.left != null) queue.add(next.left);
                if (next.right != null) queue.add(next.right);
                cur.next = next;
                cur = next;
            }
        }

        return root;
    }
}

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

答案和116一模一样

104 二叉树的最大深度

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

111 二叉树的最小深度

利用BFS查找当左右孩子都为空时的depth，不用对比，第一个找到左右都为空的时候即为最小深度，即可返回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
30


class Solution {
    public int minDepth(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 = 1;
        while (!queue.isEmpty()){
            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);
            }
            depth++;
        }

        return depth;
    }
}

226 翻转二叉树

递归写法： 前序和后序都可以，中序不行
具体实现

后序遍历 递归

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

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

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

        return root;
    }

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

前序遍历 递归

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 temp = root.left;
        root.left = root.right;
        root.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 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
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public TreeNode invertTree(TreeNode root) {

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

        while (!queue.isEmpty()){
            int length = queue.size();
            while (length-- > 0){
                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 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
17
18
19
20
21
22
23
24
25
26
27
28
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 true;
        }

        if (left != null && right == null){
            return false;
        } 
        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，可以接受null pointer， 其次，应注意if的顺序先判断是否为null再判断left和right的值是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean isSymmetric(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();

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

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

            if (leftNode == null && rightNode == null){
                continue;
            }

            if (leftNode == null && rightNode != null){
                return false;
            }
            if (leftNode != null && rightNode == null){
                return false;
            }

            if (leftNode.val != rightNode.val){
                return false;
            }

            

            queue.offer(leftNode.left);
            queue.offer(rightNode.right);
            queue.offer(leftNode.right);
            queue.offer(rightNode.left);
        }
        return true;
    }
}