111. Minimum Depth of Binary Tree

佚名 6年前 (2019-04-10) 随笔 896人围观抢沙发百度已收录

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

使用递归来做

1.如果当前结点，为null。那么最小深度depth为0

2.如果当前结点不为null，那么最小深度为1

2.1 如果左结点和右结点都为null，那么到此结束，直接返回最小深度为1

2.2 如果左结点和右结点都不为null，那么需要分别计算左结点和右结点的最小深度，取较小值+1

2.3 如果左结点不为null，右结点为null，那么左结点的最小深度+1就作为，最小深度

2.4 如果右结点不为null，左结点为null，那么右结点的最小深度+1就作为，最小深度

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

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

            int depth;
            if (left != null && right != null)
            {
                int leftDepth = MinDepth(left);
                int rightDepth = MinDepth(right);
                depth = Math.Min(leftDepth, rightDepth);
            }
            else if (left != null)
            {
                depth = MinDepth(left);
            }
            else
            {
                depth = MinDepth(right);
            }

            return depth + 1;
        }

简化版的

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

            TreeNode left = root.left;
            TreeNode right = root.right;

            if (left == null)
            {
                return MinDepth(right) + 1;
            }

            if (right == null)
            {
                return MinDepth(left) + 1;
            }

            int leftDepth = MinDepth(left);
            int rightDepth = MinDepth(right);
            return Math.Min(leftDepth, rightDepth) + 1;
        }