{1,2,3,4,5}2
{1,#,2,#,3}3
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int minDepth = Integer.MAX_VALUE;
public int run (TreeNode root) {
// write code here
if(root == null) return 0;
dfs(root, 1);
return minDepth;
}
private void dfs(TreeNode root, int depth) {
if(root == null) return;
if(root.left == null && root.right == null){
// 到了叶子节点，更新最小深度
minDepth = Math.min(depth, minDepth);
}else{
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
}
} 
func run( root *TreeNode ) int {
if root == nil {return 0}
if root.Left == nil && root.Right != nil {
return 1 + run(root.Right);
}
if root.Right == nil && root.Left != nil {
return 1 + run(root.Left);
}
return min(run(root.Left), run(root.Right)) + 1;
}
func min(a, b int) int {
if a < b {
return a;
}
return b;
} 
int min(int a,int b)
{
if(a<b)return a;
else return b;
}
int run(struct TreeNode* root ) {
int ans=0;
if(root)
ans++;
else
return ans;
int left=run(root->left);
int right=run(root->right);
if(left!=0&&right!=0)
ans+=min(left,right);
else if(left==0&&right!=0)
ans+=right;
else if(left!=0&&right==0)
ans+=left;
return ans;
}
送给考研的C语言
前序遍历二叉树。遇到叶子节点更新叶子节点的最小层数即可。
import java.util.*;
public class Solution {
int level = Integer.MAX_VALUE;
public int run (TreeNode root) {
if(root == null) return 0;
preOrder(root, 1);
return level;
}
public void preOrder(TreeNode root, int cur) {
if(root != null) {
if(root.left == null && root.right == null) {
level = Math.min(level, cur);
}
preOrder(root.left, cur + 1);
preOrder(root.right, cur + 1);
}
}
}
from os import remove # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型 # class Solution: def run(self , root: TreeNode) -> int: # write code here if root is None: return 0 res, meet = self.tranverse(root) if not meet: return 1 return res def tranverse(self, root): if root is None: return 0,False if root.left is None and root.right is None: # print(root.val) return 1,True l_res, l_meet = self.tranverse(root.left) r_res, r_meet = self.tranverse(root.right) if l_meet and r_meet: return min(l_res, r_res) + 1, True elif l_meet: return l_res + 1, True elif r_meet: return r_res + 1, True return 0,False
/**
* #[derive(PartialEq, Eq, Debug, Clone)]
* pub struct TreeNode {
* pub val: i32,
* pub left: Option<Box<TreeNode>>,
* pub right: Option<Box<TreeNode>>,
* }
*
* impl TreeNode {
* #[inline]
* fn new(val: i32) -> Self {
* TreeNode {
* val: val,
* left: None,
* right: None,
* }
* }
* }
*/
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
pub fn run(&self, root: Option<Box<TreeNode>>) -> i32 {
// write code here
Self::depth_first_traversal(&root, 0).unwrap()
}
fn depth_first_traversal(node: &Option<Box<TreeNode>>, depth: i32) -> Option<i32> {
if node.is_none() {return Some(depth)}
if node.as_ref()?.left.is_none() && node.as_ref()?.right.is_none() {
return Some(depth + 1);
}
use std::cmp::min;
use std::i32::MAX;
Some(min(
if node.as_ref()?.left.is_some() {
Self::depth_first_traversal(&node.as_ref()?.left, depth + 1)?
} else {
MAX
},
if node.as_ref()?.right.is_some() {
Self::depth_first_traversal(&node.as_ref()?.right, depth + 1)?
} else {
MAX
},
))
}
} 
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 二叉树的后续遍历，顺序是左孩子 - 右孩子 - 根节点
* 非递归遍历时，栈中始终保存根节点序列，
* 因此当访问的节点是叶子节点时，栈的大小 = 深度 - 1
* 遍历的过程中维护一个深度最小值即可
*/
int run(TreeNode* root) {
if (root == nullptr) {
return 0;
}
stack<TreeNode*> s;
int min_depth = 7000;
TreeNode* pre = root;
TreeNode* temp = root;
while (root || !s.empty()) {
while (root) {
s.push(root);
root = root->left;
}
temp = s.top();
s.pop();
// 当前节点无右孩子，或者右孩子已经被访问过，那么应该访问当前节点
if (temp->right == nullptr || temp->right == pre) {
if (temp->left == nullptr && temp->right == nullptr) {
min_depth = min(min_depth, int(s.size()) + 1);
}
pre = temp;
// 当前节点有右孩子，且右孩子尚未被访问过，
// 那么访问右孩子和右子树
} else {
s.push(temp);
root = temp->right;
}
}
return min_depth;
}
}; 
package main
import _"fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
func run( root *TreeNode ) int {
if root==nil{
return 0
}
ans:=1
q:=[]*TreeNode{root}
for len(q)>0{
new_q:=[]*TreeNode{}
for _,qi:=range q{
if qi.Left==nil&&qi.Right==nil{
return ans
}
if qi.Left!=nil{
new_q=append(new_q,qi.Left)
}
if qi.Right!=nil{
new_q=append(new_q,qi.Right)
}
}
ans++
q=new_q
}
return ans
} 
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int dfs(struct TreeNode* root){
if(NULL==root)
return 0;
else{
if(root->left==NULL && root->right!=NULL)
return dfs(root->right)+1;
if(root->right==NULL && root->left!=NULL)
return dfs(root->left)+1;
if(root->right==NULL && root->left==NULL)
return 1;
return (dfs(root->left)<dfs(root->right)?dfs(root->left):dfs(root->right))+1;
}
}
int run(struct TreeNode* root ) {
// write code here
if(root==NULL)
return 0;
// if(root->left==NULL)
// return dfs(root->right)+1;
// if(root->right==NULL)
// return dfs(root->left)+1;
return dfs(root);
} class Solution: def run(self , root: TreeNode) -> int: # write code here if not root: return 0 ans = 0 q = [] q.append(root) while len(q) and q[0]: ans += 1 size = len(q) for _ in range(size): cur = q.pop(0) if (not cur.left) and (not cur.right): return ans if cur.left: q.append(cur.left) if cur.right: q.append(cur.right)
import java.util.*;
public class Solution {
public int run (TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int depth = root.left == null ? Integer.MAX_VALUE : this.run(root.left);
if (root.right != null) {
depth = Math.min(depth, this.run(root.right));
}
return depth + 1;
}
} 
function run( root ) {
// write code here
let queue = [];
let count = 0;
if(root==null) return count;
queue.push(root);
while(queue.length>0){
let len = queue.length;
count++;
while(len--){
let node = queue.shift();
if(node.left==null&&node.right==null) return count;
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
}
return count;
} # BFS class Solution: def run(self , root: TreeNode) -> int: # write code here if not root: return 0 queue=[] queue.append(root) res=0 depth=0 while queue: depth+=1 size=len(queue) for i in range(size): cur=queue.pop(0) if not cur.left and not cur.right: res=depth return res if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right)
class Solution: def run(self , root: TreeNode) -> int: # write code here def depth(root): if not root: return 0 if root.left and root.right: return min(depth(root.left),depth(root.right))+1 elif root.left and not root.right: return depth(root.left)+1 elif not root.left and root.right: return depth(root.right)+1 else: return 1 return depth(root)
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
