求二叉树的深度

题目描述

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

思路

  递归求解

代码

/**
 * 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
 * 
 * 思路：递归求解
 * 
 * @author XIAO
 *
 */
public class BinaryTreeDepth {
	public int TreeDepth(TreeNode root) {
		if (root == null)
			return 0;
		int left = TreeDepth(root.left);
		int right = TreeDepth(root.right);
		return left > right ? left + 1 : right + 1;
	}
}

 下面是一个跟上面类似的题目。

题目描述

  判断一棵树是不是平衡二叉树。平衡二叉树指左右子树的高度不超过1的二叉树。
思路很简单，直接贴代码。

代码

/**
 * 判断一棵树是不是平衡二叉树
 * 
 * 思路：递归求左右子树的深度，比较判断是否是平衡二叉树
 * 
 * @author XIAO
 *
 */
public class IsBalancedBinaryTree {
	public boolean IsBalanced_Solution(TreeNode root) {
		if (root == null) {
			return true;
		}
		int left = getDepth(root.left);
		int right = getDepth(root.right);
		if (Math.abs(left - right) > 1) {
			return false;
		}
		return true;
	}

	// 递归求解二叉树的深度
	private int getDepth(TreeNode node) {
		if (node == null) {
			return 0;
		}
		int left = getDepth(node.left);
		int right = getDepth(node.right);
		return left > right ? left + 1 : right + 1;
	}
}