算法训练营（day16）

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

559.N叉树的最大深度

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

给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔。

解题思路

思路一：DFS递归（直接递归）

  • 遍历每个子节点，保留每次深度比较的最大值，返回结果

思路二：BFS迭代

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

详细代码

解法一：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 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 {
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        int maxDep = 0;
        for(Node node : root.children){
            maxDep = Math.max(maxDep, maxDepth(node));
        }
        return maxDep + 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
/*
// 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 {
    Deque<Node> queue = new ArrayDeque<>();
    int deep = 0;
    public int maxDepth(Node root) {
        BFS(root);
        return deep;
    }
    public void BFS(Node node){
        if(node == null){
            return;
        }
        queue.offer(node);

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                Node tmpNode = queue.poll();
                if(tmpNode.children == null || tmpNode.children.size() == 0){
                    continue;
                }
                for(Node child : tmpNode.children){
                    if(child != null){
                        queue.offer(child);
                }
                }
            }
            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);
                }
            }
        }
    }
}

222.完全二叉树的节点个数

题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/description/

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

解题思路

思路一：递归

  • 直接计算 left 和 right 节点的个数，最后进行相加

思路二：DFS递归

  • 因为是 完全二叉树 ，可以取巧计算左右节点的 深度

    • 深度相等，则说明左子树满足 2^leftDep，右子树有可能缺少节点
    • 深度不相等，则说明左子树比右子树多了一行，右子树满足 2^rightDep

  • 递归另一半子树的节点个数再相加即可

思路三：BFS迭代

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

详细代码

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 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 {
    public int countNodes(TreeNode root) {
        if (root == null){
            return 0;
        }

        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);

        if (leftDepth == rightDepth){
            return (1 << leftDepth) + countNodes(root.right);
        }else {
            return (1 << rightDepth) + countNodes(root.left);
        }

    }

    public int getDepth(TreeNode root){
        int depth = 0;
        while (root != null){
            root = root.left;
            depth++;
        }
        return 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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 count = 0;
    public int countNodes(TreeNode root) {
        BFS(root);
        return count;
    }
    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();
                count++;

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

        }
    }
}