面试大总结之二：Java搞定面试中的二叉树题目(六)
e;
}
// 先尝试在左子树中查找
boolean found = findNodeRec(root.left, node);
if (!found) { // 如果查找不到，再在右子树中查找
found = findNodeRec(root.right, node);
}
return found;
}
// 求二叉树中两个节点的最低公共祖先节点 （更加简洁版的递归）
public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) {
if(root == null){
return null;
}
// 如果有一个match，则说明当前node就是要找的最低公共祖先
if(root.equals(n1) || root.equals(n2)){
return root;
}
TreeNode commonInLeft = getLastCommonParentRec2(root.left, n1, n2);
TreeNode commonInRight = getLastCommonParentRec2(root.right, n1, n2);
// 如果一个左子树找到，一个在右子树找到，则说明root是唯一可能的最低公共祖先
if(commonInLeft!=null && commonInRight!=null){
return root;
}
// 其他情况是要不然在左子树要不然在右子树
if(commonInLeft != null){
return commonInLeft;
}
return commonInRight;
}
/**
* 非递归解法：
* 先求从根节点到两个节点的路径，然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点
*/
public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {
if (root == null || n1 == null || n2 == null) {
return null;
}
ArrayList p1 = new ArrayList();
boolean res1 = getNodePath(root, n1, p1);
ArrayList p2 = new ArrayList();
boolean res2 = getNodePath(root, n2, p2);
if (!res1 || !res2) {
return null;
}
TreeNode last = null;
Iterator iter1 = p1.iterator();
Iterator iter2 = p2.iterator();
while (iter1.hasNext() && iter2.hasNext()) {
TreeNode tmp1 = iter1.next();
TreeNode tmp2 = iter2.next();
if (tmp1 == tmp2) {
last = tmp1;
} else { // 直到遇到非公共节点
break;
}
}
return last;
}
// 把从根节点到node路径上所有的点都添加到path中
private static boolean getNodePath(TreeNode root, TreeNode node, ArrayList path) {
if (root == null) {
return false;
}
path.add(root); // 把这个节点加到路径中
if (root == node) {
return true;
}
boolean found = false;
found = getNodePath(root.left, node, path); // 先在左子树中找
if (!found) { // 如果没找到，再在右子树找
found = getNodePath(root.right, node, path);
}
if (!found) { // 如果实在没找到证明这个节点不在路径中，说明刚才添加进去的不是路径上的节点，删掉！
path.remove(root);
}
return found;
}
/**
* 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter)
* 递归解法：
* （1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
* （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，
* 要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，
* 同时记录左子树和右子树节点中到根节点的最大距离。
*
* http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.
html
*
* 计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离
*/
public static Result getMaxDistanceRec(TreeNode root){
if(root == null){
Result empty = new Result(0, -1); // 目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0
return empty;
}
// 计算出左右子树分别最大距离
Result lmd = getMaxDistanceRec(root.left);
Result rmd = getMaxDistanceRec(root.right);
Result res = new Result();
res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1; // 当前最大深度
// 取情况A和情况B中较大值
res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );
return res;
}
private static class Result{
int maxDistance;
int maxDepth;
public Result() {
}
public Result(int maxDistance, int maxDepth) {
this.maxDistance = maxDistance;
this.maxDepth = maxDepth;
}
}
/**
* 13. 由前序遍历序列和中序遍历序列重建二叉树（递归）
* 感觉这篇是讲的最为清晰的:
* http://crackinterviewtoday.wordpress.com/2010