二叉树最大深度
后序递归
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
先序递归
private int result = 0;
public int maxDepth(TreeNode root) {
if(root == null) {
return result;
}
depth(root, 1);
return result;
}
private void depth(TreeNode node, int depth) {
if(node.left == null && node.right == null) {
result = Math.max(result, depth);
return;
}
if(node.left != null) {
depth(node.left, depth + 1);
}
if(node.right != null) {
depth(node.right, depth + 1);
}
}
迭代法
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList();
int result = 0;
if(root == null) {
return 0;
}
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
result++;
while(size-- > 0) {
TreeNode tmp = queue.poll();
if(tmp.left != null) {
queue.offer(tmp.left);
}
if(tmp.right != null) {
queue.offer(tmp.right);
}
}
}
return result;
}
最小深度
后序
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null) {
return minDepth(root.right) + 1;
}
if(root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
先序
private int result ;
public int minDepth(TreeNode root) {
result = Integer.MAX_VALUE;
if(root == null) {
return 0;
}
depth(root, 1);
return result;
}
private void depth(TreeNode node, int depth) {
if(node.left == null && node.right == null) {
result = Math.min(result, depth);
return;
}
if(node.left != null) {
depth(node.left, depth + 1);
}
if(node.right != null) {
depth(node.right, depth + 1);
}
}
二叉树节点个数
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left != null) { // 求左子树深度
left = left.left;
leftDepth++;
}
while (right != null) { // 求右子树深度
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0
}
return countNodes(root.left) + countNodes(root.right) + 1;
}