输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
//方案一:
public class Solution {
int max=0;
int temp=0;
public int TreeDepth(TreeNode root) {
f(root);
return max;
}
public void f(TreeNode root){
if(root==null){
if(temp>max)
max=temp;
return;
}
temp++;
f(root.left);
f(root.right);
temp--;
}
}
//方案二:
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
return (1+TreeDepth(root.left))>(1+TreeDepth(root.right))?(1+TreeDepth(root.left)):(1+TreeDepth(root.right));
}
}
//方案三 层序遍历非递归
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
int count=0;
int curCount=1;
int nextCount=0;
int totalCount=0;
if(root==null)
return totalCount;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp=queue.remove();
count++;
if(temp.left!=null){
nextCount++;
queue.add(temp.left);
}
if(temp.right!=null){
nextCount++;
queue.add(temp.right);
}
if(count==curCount){
totalCount++;
count=0;
curCount=nextCount;
nextCount=0;
}
}
return totalCount;
}
}
//方案四:类似先序遍历,实际上线找右子树的最大高度,再找左子树的最大高度
//也可以先左子树进栈,然后右子树进栈,也就是先找左子树的最大高度,再找右子树的最大高度
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
int max=0;
if(root==null)
return max;
Stack<TreeNode> stack1=new Stack<TreeNode>();
stack1.push(root);
Stack<Integer> stack2=new Stack<Integer>();
stack2.push(0);
while(!stack1.isEmpty()){
TreeNode temp = stack1.pop();
int num=stack2.pop();
num++;
if(num>max)
max=num;
if(temp.left!=null){
stack1.push(temp.left);
stack2.push(num);
}
if(temp.right!=null){
stack1.push(temp.right);
stack2.push(num);
}
}
return max;
}
}