题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
递归1
public int getTreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;
}
递归2
public class TreeDepth {
public int TreeDepthdd(treeNode root) {
if(root == null) return 0;
int nLeft = TreeDepthdd(root.left);
int nRight = TreeDepthdd(root.right);
return nLeft > nRight ? nLeft + 1: nRight + 1;
}
}
循环
import java.util.*;
/**
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;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = null;
stack.push(root);
int depright = 0,depleft = 0;
while (!stack.isEmpty()) {
currentNode = stack.pop();
if (currentNode.right != null) {
stack.push(currentNode.right);
depright++;
}
if (currentNode.left != null) {
stack.push(currentNode.left);
depleft++;
}
}
return Math.max(depright,depleft) + 1;
}
}
