面试大总结之二：Java搞定面试中的二叉树题目(三)
c static TreeNode convertBST2DLLSubRec(TreeNode root){
if(root==null || (root.left==null && root.right==null)){
return root;
}
TreeNode tmp = null;
if(root.left != null){ // 处理左子树
tmp = convertBST2DLLSubRec(root.left);
while(tmp.right != null){ // 寻找最右节点
tmp = tmp.right;
}
tmp.right = root; // 把左子树处理后结果和root连接
root.left = tmp;
}
if(root.right != null){ // 处理右子树
tmp = convertBST2DLLSubRec(root.right);
while(tmp.left != null){ // 寻找最左节点
tmp = tmp.left;
}
tmp.left = root; // 把右子树处理后结果和root连接
root.right = tmp;
}
return root;
}
/**
* 将二叉查找树变为有序的双向链表 迭代解法
// * 类似inorder traversal的做法
*/
public static TreeNode convertBST2DLL(TreeNode root) {
if(root == null){
return null;
}
Stack stack = new Stack();
TreeNode cur = root; // 指向当前处理节点
TreeNode old = null; // 指向前一个处理的节点
TreeNode head = null; // 链表头
while( true ){
while(cur != null){ // 先添加一个非空节点所有的左孩子到栈
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()){
break;
}
// 因为此时已经没有左孩子了，所以输出栈顶元素
cur = stack.pop();
if(old != null){
old.right = cur;
}
if(head == null){ // /第一个节点为双向链表头节点
head = cur;
}
old = cur; // 更新old
cur = cur.right; // 准备处理右子树
}
return head;
}
/**
* 求二叉树第K层的节点个数 递归解法：
* （1）如果二叉树为空或者k<1返回0
* （2）如果二叉树不为空并且k==1，返回1
* （3）如果二叉树不为空且k>1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和
*
* 求以root为根的k层节点数目 等价于 求以root左孩子为根的k-1层（因为少了root那一层）节点数目 加上
* 以root右孩子为根的k-1层（因为少了root那一层）节点数目
*
* 所以遇到树，先把它拆成左子树和右子树，把问题降解
*
*/
public static int getNodeNumKthLevelRec(TreeNode root, int k) {
if (root == null || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
int numLeft = getNodeNumKthLevelRec(root.left, k - 1); // 求root左子树的k-1层节点数
int numRight = getNodeNumKthLevelRec(root.right, k - 1); // 求root右子树的k-1层节点数
return numLeft + numRight;
}
/**
* 求二叉树第K层的节点个数 迭代解法：
* 同getDepth的迭代解法
*/
public static int getNodeNumKthLevel(TreeNode root, int k){
if(root == null){
return 0;
}
Queue queue = new LinkedList();
queue.add(root);
int i = 1;
int currentLevelNodes = 1; // 当前Level，node的数量
int nextLevelNodes = 0; // 下一层Level，node的数量
while( !queue.isEmpty() && i
queue = new LinkedList();
queue.add(root);
int leafNodes = 0; // 记录上一个Level，node的数量
while( !queue.isEmpty() ){
TreeNode cur = queue.remove(); // 从队头位置移除
if(cur.left != null){ // 如果有左孩子，加到队尾
queue.add(cur.left);
}
if(cur.right != null){ // 如果有右孩子，加到队尾
queue.add(cur.right);
}
if(cur.left==null && cur.right==null){ // 叶子节点
leafNodes++;
}
}
return leafNodes;
}
/**
* 判断两棵二叉树是否相同的树。
* 递归解法：
* （1）如果两棵二叉树都为空，返回真
* （2）如果两棵二叉树一棵为空，另一棵不为空，返回假
* （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
*/
public static boolean isSameRec(TreeNode r1, TreeNode r2) {
// 如果两棵二叉树都为空，返回真
if (r1 == null && r2 == null) {
return true;
}
// 如果两棵二叉树一棵为空，另一棵不为空，返回假
else if (r1 == null || r2 == null) {
return false;
}
if(r1.val != r2.val){
return false;
}
boolean leftRes = isSameRec(r1.left, r2.left); // 比较对应左子树
boolean rightRes = isSameRec(r1.right, r2.right); // 比较对应右子树
return leftRes && rightRes;
}
/**
* 判断两棵二叉树是否相同的树（迭代）
* 遍历一遍即可，这里用preorder
*/
public static boolean isSame(TreeNode r1, TreeNode r2) {
// 如果两个树都是空树，则返回true
if(r1==null && r2==null){
return true;
}
// 如果有一棵树是空树，另一颗不是，则返回false
if(r1==null || r2==null){
return false;
}
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(r1);
s2.push(r2);
while(!s1.isEmpty() && !s2.isEmpty()){
TreeNode n1 = s1.pop();
TreeNode n2 = s2.pop();
if(n1==null && n2==null){
continue;
}else if(n1!=null && n2!=null && n1.val==n2.val){
s1.push(n1.right);
s1.push(n1.left);
s2.push(n2.right);
s2.push(n2.left);
}else{
return false;
}
}
return true;
}
/**
* 判断二叉树是不是平衡二叉树 递归解法：
* （1）如果二