LeetCode第111题 - 二叉树的最小深度

题目

解答

方案一

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

        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        root.val = 1;

        int min = Integer.MAX_VALUE;
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();

            if (node.left == null && node.right == null) {
                min = Math.min(min, node.val);
                continue;
            }

            if (node.left != null) {
                nodes.add(node.left);
                node.left.val = node.val + 1;
            }

            if (node.right != null) {
                nodes.add(node.right);
                node.right.val = node.val + 1;
            }
        }

        return min;
    }
}

方案二

class Solution {
    public int order(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = order(node.left);
        int right = order(node.right);
        if (node.left != null && node.right != null) {
            return Math.min(left, right) + 1;
        }

        if (node.left != null) {
            return left + 1;
        }

        return right + 1;
    }

    public int minDepth(TreeNode root) {
        return order(root);
    }
}

要点

方案一不够优雅，全量计算了所有节点的路径长度，同时复用树节点中的val字段来保存数据。

依据树的递归定义，符合要求的节点要么在左子树，要么在右子树，因此可以利用这个特点，递归的针对树的每个节点的左、右子树，分别求解其最小深度值。这时注意需要针对非叶子节点做特殊的处理，假如某节点的左子树或者右子树为空，此时该节点不参与本计算。文章来源地址https://www.toymoban.com/news/detail-813796.html

到了这里，关于LeetCode第111题 - 二叉树的最小深度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！