算法题/树的BFS：二叉树的最小均值

题目

求二叉树的最小深度。最小深度是指从根节点到最近的叶节点的最短路径上的节点数。 相似问题：求二叉树的最大深度。最小深度是指从根节点到最远的叶节点的最长路径上的节点数。

解答

Java

import java.util.*;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
};

class MinimumBinaryTreeDepth {
  public static int findDepth(TreeNode root) {
    if (root == null)
      return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int minimumTreeDepth = 0;
    while (!queue.isEmpty()) {
      minimumTreeDepth++;
      int levelSize = queue.size();
      for (int i = 0; i < levelSize; i++) {
        TreeNode currentNode = queue.poll();

        //检查当前节点是不是叶子结点
        if (currentNode.left == null && currentNode.right == null)
          return minimumTreeDepth;

        //插入当前节点的叶子结点到队列中
        if (currentNode.left != null)
          queue.add(currentNode.left);
        if (currentNode.right != null)
          queue.add(currentNode.right);
      }
    }
    return minimumTreeDepth;
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree Minimum Depth: " + MinimumBinaryTreeDepth.findDepth(root));
    root.left.left = new TreeNode(9);
    root.right.left.left = new TreeNode(11);
    System.out.println("Tree Minimum Depth: " + MinimumBinaryTreeDepth.findDepth(root));
  }
}

JavaScript

class TreeNode {
  constructor(x) {
    this.val = x;
    this.left = null;
    this.right = null;
  }
}

class MinimumBinaryTreeDepth {
  static findDepth(root) {
    if (root === null) {
      return 0;
    }

    const queue = [];
    queue.push(root);
    let minimumTreeDepth = 0;

    while (queue.length > 0) {
      minimumTreeDepth++;
      const levelSize = queue.length;

      for (let i = 0; i < levelSize; i++) {
        const currentNode = queue.shift();

        // 检查当前节点是不是叶子结点
        if (currentNode.left === null && currentNode.right === null) {
          return minimumTreeDepth;
        }

        // 插入当前节点的叶子结点到队列中
        if (currentNode.left !== null) {
          queue.push(currentNode.left);
        }

        if (currentNode.right !== null) {
          queue.push(currentNode.right);
        }
      }
    }

    return minimumTreeDepth;
  }
}

const root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);
console.log("Tree Minimum Depth: " + MinimumBinaryTreeDepth.findDepth(root));
root.left.left = new TreeNode(9);
root.right.left.left = new TreeNode(11);
console.log("Tree Minimum Depth: " + MinimumBinaryTreeDepth.findDepth(root));

Python

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class MinimumBinaryTreeDepth:
    def findDepth(root):
        if root is None:
            return 0

        queue = deque()
        queue.append(root)
        minimumTreeDepth = 0

        while queue:
            minimumTreeDepth += 1
            levelSize = len(queue)

            for _ in range(levelSize):
                currentNode = queue.popleft()

                # 检查当前节点是不是叶子结点
                if currentNode.left is None and currentNode.right is None:
                    return minimumTreeDepth

                # 插入当前节点的叶子结点到队列中
                if currentNode.left is not None:
                    queue.append(currentNode.left)

                if currentNode.right is not None:
                    queue.append(currentNode.right)

        return minimumTreeDepth

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)
print("Tree Minimum Depth:", MinimumBinaryTreeDepth.findDepth(root))
root.left.left = TreeNode(9)
root.right.left.left = TreeNode(11)
print("Tree Minimum Depth:", MinimumBinaryTreeDepth.findDepth(root))

Go

package main

import (
	"fmt"
)

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

func findDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	queue := []*TreeNode{root}
	minimumTreeDepth := 0

	for len(queue) > 0 {
		minimumTreeDepth++
		levelSize := len(queue)

		for i := 0; i < levelSize; i++ {
			currentNode := queue[0]
			queue = queue[1:]

			// 检查当前节点是不是叶子结点
			if currentNode.left == nil && currentNode.right == nil {
				return minimumTreeDepth
			}

			// 插入当前节点的叶子结点到队列中
			if currentNode.left != nil {
				queue = append(queue, currentNode.left)
			}

			if currentNode.right != nil {
				queue = append(queue, currentNode.right)
			}
		}
	}

	return minimumTreeDepth
}

func main() {
	root := &TreeNode{val: 12}
	root.left = &TreeNode{val: 7}
	root.right = &TreeNode{val: 1}
	root.right.left = &TreeNode{val: 10}
	root.right.right = &TreeNode{val: 5}
	fmt.Println("Tree Minimum Depth:", findDepth(root))
	root.left.left = &TreeNode{val: 9}
	root.right.left.left = &TreeNode{val: 11}
	fmt.Println("Tree Minimum Depth:", findDepth(root))
}