算法训练营（day15）

二叉树层序遍历理论基础

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

二叉树的 层序遍历 的解法一般分为 递归法DFS 以及 迭代法BFS

  • DFS 为 深度优先搜索，通过定义一个逻辑，对二叉树从上至下依次循环此逻辑，最终得出结果
  • BFS 为 广度优先搜索，下图为 使用 队列 进行 广度优先遍历 的具体流程
102二叉树的层序遍历

102.二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

解题思路

思路一：DFS递归

  • 定义数组，获取每一个节点以及其子节点的值

思路二：BFS迭代

  • 通过队列逐行获取二叉树的节点值，通过数组存储

详细代码

解法一：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
36
37
38
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        DFS(root, 0);
        return res;
    }

    public void DFS(TreeNode node, Integer deep){
        if(node == null){
            return;
        }
        deep++;

        if(res.size() < deep){
            List<Integer> list = new ArrayList<>();
            res.add(list);
        }
        res.get(deep - 1).add(node.val);
        DFS(node.left, deep);
        DFS(node.right, deep);
    }
}

解法二：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        BFS(root);
        return res;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

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

            while(size-- > 0){
                TreeNode tmp = queue.poll();
                list.add(tmp.val);

                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
            res.add(list);
        }
    }
}

107.二叉树的层次遍历II

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。(即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值，通过数组存储
  3. 定义新数组，从后往前获取 原数组 的集合，实现 自底向上

详细代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> resList = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        BFS(root);
        return res;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

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

            while(size-- > 0){
                TreeNode tmpNode = queue.poll();
                list.add(tmpNode.val);

                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
            }
            resList.add(list);
        }

        //反转
        for(int i = resList.size() - 1; i >= 0; i--){
            res.add(resList.get(i));
        }
    }
}

199.二叉树的右视图

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/description/

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值
  3. 当取到每行的最后一个节点值时，通过数组存储

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();

    public List<Integer> rightSideView(TreeNode root) {
        BFS(root);
        return res;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode tmpNode = queue.poll();
                if(i == size - 1){
                    res.add(tmpNode.val);
                }
                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
            }
        }

    }
}

637.二叉树的层平均值

题目链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值
  3. 将每行的所有节点值相加后求平均值，再通过数组存储

详细代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Double> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        BFS(root);
        return res;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            double sum = 0.0;

            for(int i = 0; i < size; i++){
                TreeNode tmpNode = queue.poll();
                sum += tmpNode.val;
                if(i == size - 1){
                    sum /= size;
                }

                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
            }
            res.add(sum);
        }
    }
}

429.N叉树的层序遍历

题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

给定一个 N 叉树，返回其节点值的层序遍历。(即从左到右，逐层遍历)。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔。

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取N叉树的节点值，通过数组存储
    • N叉树没有 left 和 right，只有 children
    • children 不仅仅只有两条，所以判 叶子节点全为空 时要确保整个 N叉树 已经遍历完全
    • 若未遍历完全，应使用 continue 保持遍历

详细代码

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
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();

    public List<List<Integer>> levelOrder(Node root) {
        BFS(root);
        return res;
    }

    public void BFS(Node node){
        if(node == null){
            return;
        }
        queue.offer(node);

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

            for(int i = 0; i < size; i++){
                Node tmpNode = queue.poll();
                list.add(tmpNode.val);

                List<Node> children = tmpNode.children;
                if(children == null || children.size() == 0){
                    continue;
                }
                for(Node child : children){
                    if(child != null){
                        queue.offer(child);
                    }
                }
            }
            res.add(list);
        }
    }
}

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

题目链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值
  3. 两两比较节点值大小，将每行最大值通过数组存储

详细代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();

    public List<Integer> largestValues(TreeNode root) {
        BFS(root);
        return res;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            int num = Integer.MIN_VALUE;

            for(int i = 0; i < size; i++){
                TreeNode tmpNode = queue.poll();
                num = Math.max(num, tmpNode.val);

                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
            }
            res.add(num);
        }
    }
}

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

题目链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解题思路

解题过程：

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值
  3. 连续从队列中取两个节点值 tmpNode 和 next
    • 让 tmpNode 指针指向其下一个右侧节点 next
  4. 一直循环，直至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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    Queue<Node> queue = new LinkedList<>();

    public Node connect(Node root) {
        BFS(root);
        return root;
    }

    public void BFS(Node node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            Node tmpNode = queue.poll();

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

            for(int i = 1; i < size; i++){
                Node next = queue.poll();
                tmpNode.next = next;
                tmpNode = next;

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

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

题目链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/?orderBy=most_votes

给定一个二叉树（和116相比，非完全二叉树）

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解题思路

解题过程：和116一致

  1. 使用 BFS迭代法 进行遍历
  2. 通过队列逐行获取二叉树的节点值
  3. 连续从队列中取两个节点值 tmpNode 和 next
    • 让 tmpNode 指针指向其下一个右侧节点 next
  4. 一直循环，直至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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    Queue<Node> queue = new LinkedList<>();

    public Node connect(Node root) {
        BFS(root);
        return root;
    }

    public void BFS(Node node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            Node tmpNode = queue.poll();

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

            for(int i = 1; i < size; i++){
                Node next = queue.poll();

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

                tmpNode.next = next;
                tmpNode = next;
            }
        }
    }
}

104.二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

解题思路

思路一：递归

  • 直接计算 left 和 right 节点的长度，最后进行比较

思路二：DFS递归

  • 同样计算 左右 节点的长度，只保留每次比较的最大值，最后直接返回

思路三：BFS迭代

  • 通过队列逐行获取二叉树的节点值
  • 每获取一行节点值，deep增加 1
  • 遍历结束，deep 即为最大值

详细代码

解法一：递归

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return deepLen(root, 1);
    }
    public int deepLen(TreeNode root, int deep){
        if(root == null){
            return deep - 1;
        }
        return Math.max(deepLen(root.left, deep + 1), deepLen(root.right, deep + 1));
    }
}

解法二：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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDep = 0;
    public int maxDepth(TreeNode root) {
        DFS(root, 0);
        return maxDep;
    }
    
    public void DFS(TreeNode node, int deep){
        if(node == null){
            return;
        }
        deep++;
        maxDep = Math.max(deep, maxDep);
        DFS(node.left, deep);
        DFS(node.right, deep);
        deep--;
    }
}

解法三：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Queue<TreeNode> queue = new LinkedList<>();
    int deep = 0;

    public int maxDepth(TreeNode root) {
        BFS(root);
        return deep;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);
        

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

111.二叉树的最小深度

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

解题思路

思路一：递归

  • 直接计算 left 和 right 节点的长度，最后进行比较

思路二：DFS递归

  • 同样计算 左右 节点的长度，当遍历到叶子节点时，保留比较的最小值，最后直接返回

思路三：BFS迭代

  • 定义最小值变量 minDep，令其初始值为 Integer.MAX_VALUE

  • 通过队列逐行获取二叉树的节点值

  • 每获取一行节点值，deep增加 1

  • 当遍历到叶子节点时，保留 deep和 minDep 比较的最小值

  • 返回 minDep

详细代码

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftDep = minDepth(root.left);
        int rightDep = minDepth(root.right);

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

        return Math.min(leftDep, rightDep) + 1;
    }
}

解法二：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
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int minDep = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        DFS(root, 1);
        return minDep;
    }

    public void DFS(TreeNode node, int deep){
        if(node == null || (node.left == null && node.right == null)){
            minDep = Math.min(deep, minDep);
        }
        if(deep < minDep){
            if(node.left != null){
                DFS(node.left, deep + 1);
            }
            if(node.right != null){
                DFS(node.right, deep + 1);
            }
        }
    }
}

解法三：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Queue<TreeNode> queue = new LinkedList<>();
    int minDep = Integer.MAX_VALUE;
    int deep = 0;

    public int minDepth(TreeNode root) {
        BFS(root);
        return minDep == Integer.MAX_VALUE ? 0 : minDep;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            deep++;

            for(int i = 0; i < size; i++){
                TreeNode tmpNode = queue.poll();

                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
                if(tmpNode.left == null && tmpNode.right == null){
                    minDep = Math.min(deep, minDep);
                }
            }
        }
    }
}

226.翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/description/

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路

思路一：递归

  • 直接翻转 左右节点

思路二：DFS递归

  • 定义逻辑：先翻转 root的左右节点，再翻转 左右节点 的 左右节点

思路三：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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(tmp);
        return root;
    }
}

解法二：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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        DFS(root);
        return root;
    }
    public void DFS(TreeNode node){
        if(node == null){
            return;
        }
        TreeNode tmp = node.right;
        DFS(node.left);
        DFS(tmp);
        node.right = node.left;
        node.left = tmp;
    }
}

解法三：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Queue<TreeNode> queue = new LinkedList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();	//更快，空间复杂度更低

    public TreeNode invertTree(TreeNode root) {
        BFS(root);
        return root;
    }

    public void BFS(TreeNode node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                TreeNode tmpNode = queue.poll();
                swap(tmpNode);
                if(tmpNode.left != null){
                    queue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.offer(tmpNode.right);
                }
            }
        }
    }

    public void swap(TreeNode node){
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;
    }
}

101.对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/description/

给定一个二叉树，检查它是否是镜像对称的。

解题思路

思路一：DFS递归

  • 定义逻辑：判断 root的左右节点是否相等，再判断 左右节点 的 左右节点 是否相等
    • 左.左 = 右.右?
    • 左.右 = 右.左?

思路二：BFS迭代

  • 通过队列获取二叉树的 左右节点
  • 依次弹出 左右节点
    • 判断 左右节点 是否相等
  • 再获取 左右节点 的 左右节点
  • 循环比较

详细代码

解法一：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
36
37
38
39
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return DFS(root.left, root.right);
    }

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

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


}

解法二：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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Queue<TreeNode> queue = new LinkedList<>();

    public boolean isSymmetric(TreeNode root) {
        return BFS(root);
    }

    public boolean BFS(TreeNode node){
        if(node == null || (node.left == null && node.right == null)){
            return true;
        }
        queue.offer(node.left);
        queue.offer(node.right);

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

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

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