大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 二叉树的递归遍历以及最大深度的求解(Java)

二叉树的递归遍历以及最大深度的求解(Java)


[摘要]本文主要是对二叉树的递归遍历以及最大深度的求解(Java)的讲解,希望对大家学习二叉树的递归遍历以及最大深度的求解(Java)有所帮助。

  递归是非常神奇的方法,代码看起来很简洁。

  对二叉树的遍历和求最大深度可以用递归的方法,主要思路就是遍历左子树,再遍历右子树。如果左子树上面的结点,有右孩子,则调用右子树的方法;遍历到左子树的叶节点的时候,返回,开始遍历右子树。如果右子树上面的结点有左孩子,则调用左子树的方法,遍历到右子树的叶子结点的时候,程序结束。

  static void scanNodes(TreeNode root){

  if(root==null){

  return;

  }

  System.out.println(root.val); //先序遍历

  scanNodes(root.left);

  //System.out.println(root.val); 中序遍历

  scanNodes(root.right);

  //System.out.println(root.val); 后序遍历

  }

  求二叉树的最大深度,也是这个思路,只需添加个返回值即可

  static int getDepth(TreeNode root){

  if(root==null){

  return 0;

  }

  int left=getDepth(root.left);

  int right=getDepth(root.right);

  return left>right?left+1:right+1;

  }

  下面附上,完整的测试代码,里面有二叉树结点的定义,大家一看就懂

  class  TreeNode

  {

  TreeNode left;

  TreeNode right;

  int val;

  TreeNode(int val){

  this.val=val;

  }

  //返回二叉树的深度

  static int getDepth(TreeNode root){

  if(root==null){

  return 0;

  }

  int left=getDepth(root.left);

  int right=getDepth(root.right);

  return left>right?left+1:right+1;

  }

  static void scanNodes(TreeNode root){

  if(root==null){

  return;

  }

  System.out.println(root.val); //先序遍历

  scanNodes(root.left);

  //System.out.println(root.val); 中序遍历

  scanNodes(root.right);

  //System.out.println(root.val); 后序遍历

  }

  public static void main(String[] args)

  {

  TreeNode root=new TreeNode(1);

  TreeNode left1=new TreeNode(2);

  TreeNode left2=new TreeNode(3);

  TreeNode right1=new TreeNode(4);

  //创建一棵树

  root.left=left1;

  left1.right=left2;

  root.right=right1;

  scanNodes(root);

  System.out.println("树的深度是:"+getDepth(root));

  }

  }

  运行结果如下:

  1

  2

  3

  4

  树的深度是:3



相关评论