求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
来个非递归的,思路是层序遍历,找到第一个左右结点都为null的情况,就返回 import java.util.LinkedList; import java.util.Queue; public class Solution { public int run(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; int depth = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int len = queue.size(); depth++; for(int i = 0; i < len; i++){ TreeNode cur = queue.poll(); if(cur.left == null && cur.right == null) return depth; if(cur.left != null) queue.offer(cur.left); if(cur.right != null) queue.offer(cur.right); } } return 0; } }
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) return run(root.right)+1; if(root.right==null) return run(root.left)+1; return Math.min(run(root.left),run(root.right))+1; } }
public int run(TreeNode root) { if(root == null) return 0; Queue<TreeNode> q = new LinkedList<>(); int next = 0;//下一层个数 int count = 1;//当前剩余个数 int layer = 1;//当前层数 q.offer(root); while(!q.isEmpty()) { TreeNode cur = q.poll(); --count;//每弹出一个数,当前层减一 if(cur.left == null && cur.right == null) return layer; if(cur.left != null) { q.offer(cur.left); ++next;//每加入一个数,当前层+1 } if(cur.right != null) { q.offer(cur.right); ++next; } if(count == 0) {//当前层剩余个数结束时,说明已经遍历结束,进入下一层 count = next;//获取下一层个数 next = 0;//复位 ++layer; //遍历下一层,层数加1 } } return layer; }2.递归版本
public int run(TreeNode root) { if(root == null) return 0; int left = run(root.left); int right = run(root.right); if(left == 0 || right == 0) return left + right + 1; return Math.min(left, right) + 1; }
class Solution {
public:
int run(TreeNode *root) {
if (root == NULL) { return 0; }
if (root->left and root->right) {
return min(run(root->left), run(root->right)) + 1;
} else if (root->left) {
return run(root->left) + 1;
} else if (root->right) {
return run(root->right) + 1;
} else { return 1; }
}
};
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; } };