输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

//方案一:

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;
}

}

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看