VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 111. 二叉树的最小深度

Posted on Edited on In , ,

摘要：
树的深度计算。

题目

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

示例:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最小深度 2.

二叉树定义：

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

本题考查树深度，考虑到树结构的递归特性，可以很容易利用递归去计算。

DFS

当root节点左右孩子都非空时，二叉树深度最小当且仅当root的左右孩子节点深度取最小。另外，root为空或者root的左或右孩子节点为空的情况可以很容易判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * 2021-6-25 15:21:19
 * author: etoa
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int lheight = minDepth(root->left);
        int rheight = minDepth(root->right);
        int height;
        if ((!lheight && !rheight) || (lheight && rheight)) {   // 在某个节点的左右子树都有深度或者都没有深度的情况下，取较小的
            height = min(lheight, rheight);
        }
        else {                                                 // 否则，左右子树有一个没有深度，那么就不能取较小的，而是取较大的
            height = max(lheight, rheight);
        }
        return height + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs(root);
    }
    private int dfs(TreeNode node) {
        if (node.left == null && node.right == null) {
            return 1;
        }
        if (node.left == null) {                                // 左边没有深度，右边有深度，不能取较小的，而是取右边的深度
            return dfs(node.right) + 1;
        }
        if (node.right == null) {                               // 右边没有深度，左边有深度，不能取较小的，而是取左边的深度
            return dfs(node.left) + 1;
        }
        return Math.min(dfs(node.left), dfs(node.right)) + 1;   // 左右都有深度，取较小的
    }
}

另外，我们亦可维护一个 最小值变量，通过不断和其比较最终得出最小深度。该方法参考官方题解。
注意这个最小值变量不是全局的，而是对于某一层递归产生一个最小值，即左右子树深度和该最小值比较返回至上一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }
        return min_depth + 1; //+1为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
27
28
29
30
31
32
33
34
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return bfs(root);
    }
    private int bfs(TreeNode node) {
        int ans = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {  //size > 0保证一行可以被完全访问
                TreeNode cur_node = queue.poll();
                size--;
                TreeNode left = cur_node.left;
                TreeNode right = cur_node.right;
                if (left == null && right == null) {
                    return ans;
                }
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            //while size == 0, column over
            ans++;
        }
        return ans;   
    }
}

亦可自定义包含深度信息的节点类，此方法参考官方题解。

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 {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

原题链接： LeetCode 111. 二叉树的最小深度