Ввод: root = [8,null,4,null,null,9]
Вывод: 3
Объяснение: в деревe только один лист - вершина со значением 9, а минимальный путь до нее от корня это 3
Ограничения:
Число узлов в дереве >= 1
Высота дерева <= 1000
Значение вершин дерева лежит в диапазоне [-10 000, 10 000] (включительно)
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
private static bool IsLeaf(TreeNode node)
{
return node.left == null && node.right == null;
}
private static int Traversal(TreeNode node)
{
if (IsLeaf(node))
{
// вершина не имеет детей (лист)
return 1;
}
else if (node.right == null)
{
// вершина имеет только левого ребенка
return 1 + Traversal(node.left);
}
else if (node.left == null)
{
// вершина имеет только правого ребенка
return 1 + Traversal(node.right);
}
// вершина имеет двух детей
return 1 + Math.Min(Traversal(node.left), Traversal(node.right));
}
public static int MinDepth(TreeNode root)
{
if (root == null)
{
return 0;
}
return Traversal(root);
}
}
#include <vector>
using namespace std;
/**
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
bool isLeaf(TreeNode* node) {
return node->left == nullptr && node->right == nullptr;
}
int traversal(TreeNode* node) {
if (isLeaf(node)) {
// вершина не имеет детей (лист)
return 1;
} else if (node->right == nullptr) {
// вершина имеет только левого ребенка
return 1 + traversal(node->left);
} else if (node->left == nullptr) {
// вершина имеет только правого ребенка
return 1 + traversal(node->right);
}
// вершина имеет двух детей
return 1 + min(traversal(node->left), traversal(node->right));
}
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return traversal(root);
}
package main
/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func min(a, b int) int {
if (a < b) {
return a
}
return b
}
func isLeaf(node *TreeNode) bool {
return node.Left == nil && node.Right == nil
}
func traversal(node *TreeNode) int {
if isLeaf(node) {
// вершина не имеет детей (лист)
return 1
} else if node.Right == nil {
// вершина имеет только левого ребенка
return 1 + traversal(node.Left)
} else if node.Left == nil {
// вершина имеет только правого ребенка
return 1 + traversal(node.Right)
}
// вершина имеет двух детей
return 1 + min(traversal(node.Left), traversal(node.Right))
}
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
return traversal(root)
}
import java.util.*;
/**
* class TreeNode {
* Integer val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(Integer val) { this.val = val; }
* TreeNode(Integer val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isLeaf(TreeNode node) {
return node.left == null && node.right == null;
}
public int traversal(TreeNode node) {
if (isLeaf(node)) {
// вершина не имеет детей (лист)
return 1;
} else if (node.right == null) {
// вершина имеет только левого ребенка
return 1 + traversal(node.left);
} else if (node.left == null) {
// вершина имеет только правого ребенка
return 1 + traversal(node.right);
}
// вершина имеет двух детей
return 1 + Math.min(traversal(node.left), traversal(node.right));
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return traversal(root);
}
}
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def is_leaf(node: TreeNode) -> bool:
return node.left is None and node.right is None
def traversal(node: TreeNode) -> int:
if is_leaf(node):
# вершина не имеет детей (лист)
return 1
elif node.right is None:
# вершина имеет только левого ребенка
return 1 + traversal(node.left)
elif node.left is None:
# вершина имеет только правого ребенка
return 1 + traversal(node.right)
# вершина имеет двух детей
return 1 + min(traversal(node.left), traversal(node.right))
def min_depth(root: TreeNode) -> int:
if root is None:
return 0
return traversal(root)
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def is_leaf(node: TreeNode) -> bool:
return node.left is None and node.right is None
def traversal(node: TreeNode) -> int:
if is_leaf(node):
# вершина не имеет детей (лист)
return 1
elif node.right is None:
# вершина имеет только левого ребенка
return 1 + traversal(node.left)
elif node.left is None:
# вершина имеет только правого ребенка
return 1 + traversal(node.right)
# вершина имеет двух детей
return 1 + min(traversal(node.left), traversal(node.right))
def min_depth(root: TreeNode) -> int:
if root is None:
return 0
return traversal(root)
