求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
class Solution { public: static int depth; int run(TreeNode *root) { depth=1; if(root==NULL) return 0; if(root->left!=NULL) dfs(root->left, 1); if(root->right!=NULL) dfs(root->right, 1); return depth; } void dfs(TreeNode *r, int d) { d++; if(d>depth&&depth>1) return; if(r->left==NULL&&r->right==NULL&&(depth==1||d<depth)) { depth=d; return; } if(r->left!=NULL) dfs(r->left, d); if(r->right!=NULL) dfs(r->right, d); return; } }; int Solution::depth=1;
//层次遍历 获取第一个叶子节点 public int run(TreeNode root) { if(root==null) return 0; LinkedList<TreeNode> queue = new LinkedList<>(); int level=1; TreeNode last,now; last=now=root; queue.add(root); while(queue.size()!=0){ TreeNode node=queue.poll(); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); if(node.left==null&&node.right==null) return level; if(node==last){ level++; last=queue.getLast(); } } return level; }
三行代码搞定 public int run(TreeNode root) { if (root == null) return 0; int r = run(root.right), l = run(root.left); return r * l == 0 ? r + l + 1 : Math.min(r, l) + 1; }
采用层次遍历,如果该层有叶节点,那么最短depth到此为止,如果没有,就遍历下一层
if (root == null) //是0
return 0;
//根不空,放入
List<TreeNode> list = new ArrayList<>();
list.add(root);
int depth = 1; //根存在,设为1
int cur = 0, last = 1; //cur开始指向当前层第一个节点,last指向下一层第一个
while (cur < list.size()){
last = list.size(); //last指向下一层第一个
//访问当前层,看一看有没有叶子节点,如果有,那么最短路径就已经求出,否则路径长度加1,指向下一层
while (cur < last){
TreeNode curNode = list.get(cur); //取当前节点
if (curNode.left == null && curNode.right == null)
return depth;
else {
if (curNode.left != null)
list.add(curNode.left);
if (curNode.right != null)
list.add(curNode.right);
}
cur++; //cur指向下一个节点
}
//当前层没有叶子节点,depth + 1
depth++;
}
return depth;
递归遍历左子树和右子树,返回最小的那个,然后加一 即为树的最小深度 class Solution { public: int run(TreeNode *root) { if(root == NULL) return 0; int lmin = run(root->left); int rmin = run(root->right); if(lmin==0 && rmin == 0) return 1; if(lmin == 0) lmin = INT_MAX; if(rmin == 0) rmin = INT_MAX; return min(lmin, rmin)+1; } };
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int run (TreeNode root) { if(root == null) { return 0; } if(root.left != null && root.right != null) { return Math.min(run(root.left), run(root.right)) + 1; }else if(root.left != null) { return run(root.left) + 1; }else if(root.right != null) { return run(root.right) + 1; }else { // 该节点为叶子节点 return 1; } } }
class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int run(TreeNode* root) { // write code here if(root == nullptr) return 0; int l = run(root->left); int r = run(root->right); return 1 + (l&&r ? min(l,r) : l^r); } };
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; LinkedList<TreeNode> queue=new LinkedList<>(); queue.add(root); int count=0; while(!queue.isEmpty()){ int len=queue.size(); count++; for(int i=0; i<len; i++){ TreeNode temp=queue.remove(0); if(temp.left==null&&temp.right==null) return count; if(temp.left!=null) queue.add(temp.left); if(temp.right!=null) queue.add(temp.right); } } return count; } }
import java.util.LinkedList; public class Solution { public int run(TreeNode root) { if (root == null){ return 0; } if (root.left==null && root.right==null){ return 1; } LinkedList<TreeNode> list = new LinkedList<TreeNode>(); list.addLast(root); list.addLast(null); int deepth = 1; while (!list.isEmpty()){ TreeNode treeNode = list.pop(); if (treeNode == null){ list.addLast(null); deepth++; continue; } if (treeNode.left==null && treeNode.right==null){ return deepth; } if (treeNode.left != null){ list.addLast(treeNode.left); } if (treeNode.right != null){ list.addLast(treeNode.right); } } return deepth; } }
import sys sys.setrecursionlimit(1000000) class Solution: def run(self , root): if root is None: return 0 if root.left is None and root.right is None: return 1 if root.left is None: return 1 + self.run(root.right) if root.right is None: return 1 + self.run(root.left); return 1 + min(self.run(root.left), self.run(root.right))
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ int depth = 0; public int run (TreeNode root) { // write code here if(root == null) { return depth; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); run(queue); return depth; } public void run(Queue<TreeNode> queue) { int qsize = queue.size(); if(qsize>0) { depth++; }else { return ; } while(qsize>0) { TreeNode node = queue.poll(); System.out.println(node.val); qsize--; if(node.left == null && node.right == null) { return; } if(node.left != null){ queue.offer(node.left); } if(node.right != null) { queue.offer(node.right); } } run(queue); } }
class Solution { public: int run(TreeNode* root) { if(root == nullptr) return 0; queue<TreeNode*> q; q.push(root); int dep = 1; while(!q.empty()) { int s = q.size(); while(s--) { TreeNode* t = q.front(); q.pop(); if(t->right == nullptr && t->left == nullptr) return dep; if(t->right) q.push(t->right); if(t->left) q.push(t->left); } dep++; } return dep; } };
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int mindeepth = INT_MAX; void dfs(TreeNode* root, int deepth) { if (root == NULL) { return ; } if (root->left == NULL && root->right == NULL) { if (deepth < mindeepth) { mindeepth = deepth; } } dfs(root->left, deepth + 1); dfs(root->right, deepth + 1); } int run(TreeNode* root) { dfs(root, 1) ; return mindeepth == INT_MAX ? 0 : mindeepth; } };
int run(TreeNode* root) { // write code here if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) return 1; if(root->left==NULL&&root->right!=NULL) return 1+run(root->right); if(root->left!=NULL&&root->right==NULL) return 1+run(root->left); if(root->left!=NULL&&root->right!=NULL) return min(1+run(root->left),1+run(root->right)); }
public static int getMinDepth(Node node) { if (node == null) { return 0; } int leftDepth = getMinDepth(node.left) + 1; int rightDepth = getMinDepth(node.right) + 1; return Math.min(leftDepth, rightDepth); }修改后
public class Solution { public int run(TreeNode root) { if(root==null){ return 0; } int left = run(root.left); int right = run(root.right); if(left*right >0){//判断,如果有一端是空,是返回数字大的非空一段,因为是求到叶子节点的距离 return (left>right?right:left)+1; }else{ return (left>right?left:right)+1; } } }
思路1:递归 若空树,则返回0 若左子树为空,则返回右子树最小深度+1 若右子树为空,则返回左子树最小深度+1 若左右子树均不为空,则返回左右子树较小者+1 import java.lang.Math; public class Solution { public int run(TreeNode root) { //若空树,则返回0 if(root == null) return 0; //若左子树为空,则返回右子树最小深度+1 if(root.left==null) return run(root.right)+1; //若右子树为空,则返回左子树最小深度+1 if(root.right==null) return run(root.left)+1; //若左右子树均不为空,则返回左右子树较小者+1 return (Math.min(run(root.left),run(root.right))+1); } }
思路2:层次遍历 若为空树,返回0 声明队列,头结点入队 声明深度记录变量depth -------- 若队列非空,每次处理一层的节点(即使用for循环来实现该处理)下一层节点进入队列。 判断条件:当出现节点左右子树均为空时,则此时的层数记为最短路径长。 否则,左子树、右子树进队 -------- */ import java.util.Queue; import java.util.LinkedList; public class Solution { public int run(TreeNode root) { if(root == null) return 0;//若为空树,返回0 if(root.left==null && root.right==null) return 1; //声明队列,声明深度记录变量 Queue<TreeNode> queue = new LinkedList<>(); //声明队列,头结点入队 queue.offer(root); //声明深度记录变量depth int depth = 0; while(!queue.isEmpty()){ int len = queue.size(); depth++; //若队列非空,每次处理一层的节点(即使用for循环来实现该处理)下一层节点进入队列。 for(int i=0;i<len;i++){ TreeNode curNode = queue.poll(); //判断条件:当出现节点左右子树均为空时,则此时的层数记为最短路径长。 if(curNode.left==null && curNode.right==null) return depth; //左子树非空,左子树进队 if(curNode.left != null) queue.offer(curNode.left); //右子树非空,右子树进队 if(curNode.right != null) queue.offer(curNode.right); } } return 0; } }
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int run(TreeNode root) { if(root==null) return 0; if(root.left == null && root.right == null) return 1; if(root.left != null && root.right != null) return min(run(root.left),run(root.right))+1; return max(run(root.left),run(root.right))+1; } public int min(int a,int b){ return a > b ? b : a; } public int max(int a,int b){ return a > b ? a : b; } }java递归解决,遇到空值返回0,遇到叶子节点返回1,遇到只有一个子节点的,则继续沿着子节点递归,直到遍历至叶子节点