111.二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

迭代思路

1.层级遍历二叉树，当遍历到叶子结点时，结束循环即可。

Java代码实现

    public int minDepth(TreeNode root) {
        int count = 0;
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        if(root != null)
            treeNodes.add(root);
        else
            return 0;
        int curMax = 1;
        int nodeCount=0;
        //层级遍历
        while(!treeNodes.isEmpty()){
            TreeNode cur = treeNodes.pollFirst();
            nodeCount++;
            if(cur.left == null && cur.right == null)
                break;
            if (cur.left != null)
                treeNodes.add(cur.left);
            if(cur.right != null)
                treeNodes.add(cur.right);
            if(nodeCount == curMax){
                //深度+1
                count++;
                nodeCount=0;
                curMax = treeNodes.size();
            }
        }
        return count+1;
    }

Golang代码实现

func minDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    nodeList := list.New()
    nodeList.PushBack(root)
    depth := 1
    curMax := 1
    count := 0
    for nodeList.Len() != 0 {
        count++
        curNode := nodeList.Front()
        if curNode.Value.(*TreeNode).Left == nil && curNode.Value.(*TreeNode).Right == nil{
            break
        }
        nodeList.Remove(curNode)
        if curNode.Value.(*TreeNode).Left != nil{
            nodeList.PushBack(curNode.Value.(*TreeNode).Left)
        }

        if curNode.Value.(*TreeNode).Right != nil{
            nodeList.PushBack(curNode.Value.(*TreeNode).Right)
        }
        if curMax == count{
            curMax = nodeList.Len()
            depth++
            count = 0
        }
    }
    return depth
}

递归思路

1. 递归处理没一个结点，在处理时保存并处理当前深度
2. 若当前结点是叶子结点，结束递归即可。

Java代码实现

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

    private int minDepth(TreeNode root,int depth){
        if(root.left == null && root.right == null){
            return depth+1;
        }

        if(root.left != null && root.right != null){
            return Math.min(minDepth(root.left,depth+1),minDepth(root.right,depth+1));
        }else if(root.left != null && root.right == null){
            return minDepth(root.left,depth+1);
        }else{
            return minDepth(root.right,depth+1);
        }
    }

Golang代码实现

func minDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    return minDepthDG(root,0);
}

func minDepthDG(root *TreeNode,depth int) int {
    if root.Left == nil && root.Right == nil{
        return depth+1
    }else{
        if root.Left != nil && root.Right != nil{
            leftDepth := minDepthDG(root.Left,depth+1)
            rightDepth := minDepthDG(root.Right,depth+1)

            if leftDepth<rightDepth{
                return leftDepth
            }else {
                return rightDepth
            }
        }else if root.Left == nil && root.Right != nil{
            return minDepthDG(root.Right,depth+1)
        }else {
            return minDepthDG(root.Left,depth+1)
        }
    }
}