题目描述
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
简洁代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
return leftDepth > rightDepth? leftDepth + 1:rightDepth + 1;//这里要加1的原因是深度数的是节点的个数
}
}
public class BinaryTreeDepth {
static class TreeNode{
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public int treeDepth(TreeNode root){
if(root == null){
System.out.println("root为空");
}else {
System.out.println("root--------------:" + root.val);
}
if(root == null) return 0;
int leftDepth = treeDepth(root.left);
System.out.println("leftDepth:" + leftDepth);
int rightDepth = treeDepth(root.right);
System.out.println("rightDepth:" + rightDepth);
return leftDepth > rightDepth? leftDepth + 1:rightDepth + 1;
}
public static void main(String[] args){
BinaryTreeDepth binaryTreeDepth = new BinaryTreeDepth();
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
int i = binaryTreeDepth.treeDepth(treeNode);
System.out.println(i);
}
}
root--------------:1
root--------------:2
root--------------:4
root为空
==========================左子树遍历完成
leftDepth:0==>root = 4.left
root为空
rightDepth:0=>root = 4.right
leftDepth:1==>root = 2.left = 4
root--------------:5==>2.right = 5
root为空==>root = 5.left
leftDepth:0==>root = 5.left
root为空==>root = 5.right
rightDepth:0==>root = 5.right
rightDepth:1==>root = 2.right = 5
leftDepth:2==>root = 1.left = 2<====================左子树的深度为leftDephth + 1 = 3
root--------------:3==>root = 1.right = 3
root为空==>root = 3.left
leftDepth:0==>root = 3.left
root为空==>root = 3.right
rightDepth:0==>root = 3.right
rightDepth:1==>root = 1.right = 3<====================右子树的深度为rightDepth + 1 = 2
3
Process finished with exit code 0