面试大总结之二：Java搞定面试中的二叉树题目(五)
叉树为空，返回真
* （2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
*/
public static boolean isAVLRec(TreeNode root) {
if(root == null){ // 如果二叉树为空，返回真
return true;
}
// 如果左子树和右子树高度相差大于1，则非平衡二叉树, getDepthRec()是前面实现过的求树高度的方法
if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){
return false;
}
// 递归判断左子树和右子树是否为平衡二叉树
return isAVLRec(root.left) && isAVLRec(root.right);
}
/**
* 求二叉树的镜像 递归解法：
* （1）如果二叉树为空，返回空
* （2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树
*/
// 1. 破坏原来的树，把原来的树改成其镜像
public static TreeNode mirrorRec(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorRec(root.left);
TreeNode right = mirrorRec(root.right);
root.left = right;
root.right = left;
return root;
}
// 2. 不能破坏原来的树，返回一个新的镜像树
public static TreeNode mirrorCopyRec(TreeNode root){
if(root == null){
return null;
}
TreeNode newNode = new TreeNode(root.val);
newNode.left = mirrorCopyRec(root.right);
newNode.right = mirrorCopyRec(root.left);
return newNode;
}
// 3. 判断两个树是否互相镜像
public static boolean isMirrorRec(TreeNode r1, TreeNode r2){
// 如果两个树都是空树，则返回true
if(r1==null && r2==null){
return true;
}
// 如果有一棵树是空树，另一颗不是，则返回false
if(r1==null || r2==null){
return false;
}
// 如果两个树都非空树，则先比较根节点
if(r1.val != r2.val){
return false;
}
// 递归比较r1的左子树的镜像是不是r2右子树 和
// r1的右子树的镜像是不是r2左子树
return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);
}
// 1. 破坏原来的树，把原来的树改成其镜像
public static void mirror(TreeNode root) {
if(root == null){
return;
}
Stack stack = new Stack();
stack.push(root);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop();
// 交换左右孩子
TreeNode tmp = cur.right;
cur.right = cur.left;
cur.left = tmp;
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
// 2. 不能破坏原来的树，返回一个新的镜像树
public static TreeNode mirrorCopy(TreeNode root){
if(root == null){
return null;
}
Stack
stack = new Stack();
Stack newStack = new Stack();
stack.push(root);
TreeNode newRoot = new TreeNode(root.val);
newStack.push(newRoot);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop();
TreeNode newCur = newStack.pop();
if(cur.right != null){
stack.push(cur.right);
newCur.left = new TreeNode(cur.right.val);
newStack.push(newCur.left);
}
if(cur.left != null){
stack.push(cur.left);
newCur.right = new TreeNode(cur.left.val);
newStack.push(newCur.right);
}
}
return newRoot;
}
/**
* 求二叉树中两个节点的最低公共祖先节点
* 递归解法：
* （1）如果两个节点分别在根节点的左子树和右子树，则返回根节点
* （2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树
*/
public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {
if (findNodeRec(root.left, n1)) { // 如果n1在树的左子树
if (findNodeRec(root.right, n2)) { // 如果n2在树的右子树
return root; // 返回根节点
} else { // 如果n2也在树的左子树
return getLastCommonParentRec(root.left, n1, n2); // 递归处理
}
} else { // 如果n1在树的右子树
if (findNodeRec(root.left, n2)) { // 如果n2在左子树
return root;
} else { // 如果n2在右子树
return getLastCommonParentRec(root.right, n1, n2); // 递归处理
}
}
}
// 帮助方法，递归判断一个点是否在树里
private static boolean findNodeRec(TreeNode root, TreeNode node) {
if (root == null || node == null) {
return false;
}
if (root == node) {
return tru