java——二叉树面试题
1 2 import java.util.ArrayList; 3 import java.util.Iterator; 4 import java.util.LinkedList; 5 import java.util.List; 6 import java.util.Queue; 7 import java.util.Stack; 8 9 /** 10 * http://blog.csdn.net/luckyxiaoqiang/article/details/7518888 轻松搞定面试中的二叉树题目 11 * http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html 算法大全（3） 二叉树 12 * 13 * TODO: 一定要能熟练地写出所有问题的递归和非递归做法！ 14 * 15 * 1. 求二叉树中的节点个数: getNodeNumRec（递归），getNodeNum（迭代） 16 * 2. 求二叉树的深度: getDepthRec（递归），getDepth 17 * 3. 前序遍历，中序遍历，后序遍历: preorderTraversalRec, preorderTraversal, inorderTraversalRec, postorderTraversalRec 18 * (https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2) 19 * 4.分层遍历二叉树（按层次从上往下，从左往右）: levelTraversal, levelTraversalRec（递归解法！） 20 * 5. 将二叉查找树变为有序的双向链表: convertBST2DLLRec, convertBST2DLL 21 * 6. 求二叉树第K层的节点个数：getNodeNumKthLevelRec, getNodeNumKthLevel 22 * 7. 求二叉树中叶子节点的个数：getNodeNumLeafRec, getNodeNumLeaf 23 * 8. 判断两棵二叉树是否相同的树：isSameRec, isSame 24 * 9. 判断二叉树是不是平衡二叉树：isAVLRec 25 * 10. 求二叉树的镜像（破坏和不破坏原来的树两种情况）：mirrorRec, mirrorCopyRec 26 * 10.1 判断两个树是否互相镜像：isMirrorRec 27 * 11. 求二叉树中两个节点的最低公共祖先节点：getLastCommonParent, getLastCommonParentRec, getLastCommonParentRec2 28 * 12. 求二叉树中节点的最大距离：getMaxDistanceRec 29 * 13. 由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec 30 * 14.判断二叉树是不是完全二叉树：isCompleteBinaryTree, isCompleteBinaryTreeRec 31 * 32 */ 33 public class Demo { 34 35 /* 36 1 37 / 38 2 3 39 / 40 4 5 6 41 */ 42 public static void main(String[] args) { 43 TreeNode r1 = new TreeNode(1); 44 TreeNode r2 = new TreeNode(2); 45 TreeNode r3 = new TreeNode(3); 46 TreeNode r4 = new TreeNode(4); 47 TreeNode r5 = new TreeNode(5); 48 TreeNode r6 = new TreeNode(6); 49 50 r1.left = r2; 51 r1.right = r3; 52 r2.left = r4; 53 r2.right = r5; 54 r3.right = r6; 55 56 // System.out.println(getNodeNumRec(r1)); 57 // System.out.println(getNodeNum(r1)); 58 // System.out.println(getDepthRec(r1)); 59 // System.out.println(getDepth(r1)); 60 61 // preorderTraversalRec(r1); 62 // System.out.println(); 63 // preorderTraversal(r1); 64 // System.out.println(); 65 // inorderTraversalRec(r1); 66 // System.out.println(); 67 // inorderTraversal(r1); 68 // System.out.println(); 69 // postorderTraversalRec(r1); 70 // System.out.println(); 71 // postorderTraversal(r1); 72 // System.out.println(); 73 // levelTraversal(r1); 74 // System.out.println(); 75 // levelTraversalRec(r1); 76 // System.out.println(); 77 78 // TreeNode tmp = convertBSTRec(r1); 79 // while(true){ 80 // if(tmp == null){ 81 // break; 82 // } 83 // System.out.print(tmp.val + " "); 84 // if(tmp.right == null){ 85 // break; 86 // } 87 // tmp = tmp.right; 88 // } 89 // System.out.println(); 90 // while(true){ 91 // if(tmp == null){ 92 // break; 93 // } 94 // System.out.print(tmp.val + " "); 95 // if(tmp.left == null){ 96 // break; 97 // } 98 // tmp = tmp.left; 99 // } 100 101 102 // TreeNode tmp = convertBST2DLL(r1); 103 // while(true){ 104 // if(tmp == null){ 105 // break; 106 // } 107 // System.out.print(tmp.val + " "); 108 // if(tmp.right == null){ 109 // break; 110 // } 111 // tmp = tmp.right; 112 // } 113 114 // System.out.println(getNodeNumKthLevelRec(r1, 2)); 115 // System.out.println(getNodeNumKthLevel(r1, 2)); 116 117 // System.out.println(getNodeNumLeafRec(r1)); 118 // System.out.println(getNodeNumLeaf(r1)); 119 120 // System.out.println(isSame(r1, r1)); 121 // inorderTraversal(r1); 122 // System.out.println(); 123 // mirror(r1); 124 // TreeNode mirrorRoot = mirrorCopy(r1); 125 // inorderTraversal(mirrorRoot); 126 127 System.out.println(isCompleteBinaryTree(r1)); 128 System.out.println(isCompleteBinaryTreeRec(r1)); 129 130 } 131 132 private static class TreeNode { 133 int val; 134 TreeNode left; 135 TreeNode right; 136 137 public TreeNode(int val) { 138 this.val = val; 139 } 140 } 141 142 /** 143 * 求二叉树中的节点个数递归解法： O(n) 144 * （1）如果二叉树为空，节点个数为0 145 * （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 146 * 右子树节点个数 + 1 147 */ 148 public static int getNodeNumRec(TreeNode root) { 149 if (root == null) { 150 return 0; 151 } else { 152 return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1; 153 } 154 } 155 156 /** 157 * 求二叉树中的节点个数迭代解法O(n)：基本思想同LevelOrderTraversal， 158 * 即用一个Queue，在Java里面可以用LinkedList来模拟 159 */ 160 public static int getNodeNum(TreeNode root) { 161 if(root == null){ 162 return 0; 163 } 164 int count = 1; 165 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 166 queue.add(root); 167 168 while(!queue.isEmpty()){ 169 TreeNode cur = queue.remove(); // 从队头位置移除 170 if(cur.left != null){ // 如果有左孩子，加到队尾 171 queue.add(cur.left); 172 count++; 173 } 174 if(cur.right != null){ // 如果有右孩子，加到队尾 175 queue.add(cur.right); 176 count++; 177 } 178 } 179 180 return count; 181 } 182 183 /** 184 * 求二叉树的深度（高度） 递归解法： O(n) 185 * （1）如果二叉树为空，二叉树的深度为0 186 * （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 187 */ 188 public static int getDepthRec(TreeNode root) { 189 if (root == null) { 190 return 0; 191 } 192 193 int leftDepth = getDepthRec(root.left); 194 int rightDepth = getDepthRec(root.right); 195 return Math.max(leftDepth, rightDepth) + 1; 196 } 197 198 /** 199 * 求二叉树的深度（高度） 迭代解法： O(n) 200 * 基本思想同LevelOrderTraversal，还是用一个Queue 201 */ 202 public static int getDepth(TreeNode root) { 203 if(root == null){ 204 return 0; 205 } 206 207 int depth = 0; // 深度 208 int currentLevelNodes = 1; // 当前Level，node的数量 209 int nextLevelNodes = 0; // 下一层Level，node的数量 210 211 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 212 queue.add(root); 213 214 while( !queue.isEmpty() ){ 215 TreeNode cur = queue.remove(); // 从队头位置移除 216 currentLevelNodes--; // 减少当前Level node的数量 217 if(cur.left != null){ // 如果有左孩子，加到队尾 218 queue.add(cur.left); 219 nextLevelNodes++; // 并增加下一层Level node的数量 220 } 221 if(cur.right != null){ // 如果有右孩子，加到队尾 222 queue.add(cur.right); 223 nextLevelNodes++; 224 } 225 226 if(currentLevelNodes == 0){ // 说明已经遍历完当前层的所有节点 227 depth++; // 增加高度 228 currentLevelNodes = nextLevelNodes; // 初始化下一层的遍历 229 nextLevelNodes = 0; 230 } 231 } 232 233 return depth; 234 } 235 236 237 238 /** 239 * 前序遍历，中序遍历，后序遍历 前序遍历递归解法： 240 * （1）如果二叉树为空，空操作 241 * （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 242 */ 243 public static void preorderTraversalRec(TreeNode root) { 244 if (root == null) { 245 return; 246 } 247 System.out.print(root.val + " "); 248 preorderTraversalRec(root.left); 249 preorderTraversalRec(root.right); 250 } 251 252 /** 253 * 前序遍历迭代解法：用一个辅助stack，总是把右孩子放进栈 254 * http://www.youtube.com/watch?v=uPTCbdHSFg4 255 */ 256 public static void preorderTraversal(TreeNode root) { 257 if(root == null){ 258 return; 259 } 260 261 Stack<TreeNode> stack = new Stack<TreeNode>(); // 辅助stack 262 stack.push(root); 263 264 while( !stack.isEmpty() ){ 265 TreeNode cur = stack.pop(); // 出栈栈顶元素 266 System.out.print(cur.val + " "); 267 268 // 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子 269 if(cur.right != null){ 270 stack.push(cur.right); 271 } 272 if(cur.left != null){ 273 stack.push(cur.left); 274 } 275 } 276 } 277 278 /** 279 * 中序遍历递归解法 280 * （1）如果二叉树为空，空操作。 281 * （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 282 */ 283 public static void inorderTraversalRec(TreeNode root) { 284 if (root == null) { 285 return; 286 } 287 inorderTraversalRec(root.left); 288 System.out.print(root.val + " "); 289 inorderTraversalRec(root.right); 290 } 291 292 /** 293 * 中序遍历迭代解法 ，用栈先把根节点的所有左孩子都添加到栈内， 294 * 然后输出栈顶元素，再处理栈顶元素的右子树 295 * http://www.youtube.com/watch?v=50v1sJkjxoc 296 * 297 * 还有一种方法能不用递归和栈，基于线索二叉树的方法，较麻烦以后补上 298 * http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ 299 */ 300 public static void inorderTraversal(TreeNode root){ 301 if(root == null){ 302 return; 303 } 304 Stack<TreeNode> stack = new Stack<TreeNode>(); 305 TreeNode cur = root; 306 307 while( true ){ 308 while(cur != null){ // 先添加一个非空节点所有的左孩子到栈 309 stack.push(cur); 310 cur = cur.left; 311 } 312 313 if(stack.isEmpty()){ 314 break; 315 } 316 317 // 因为此时已经没有左孩子了，所以输出栈顶元素 318 cur = stack.pop(); 319 System.out.print(cur.val + " "); 320 cur = cur.right; // 准备处理右子树 321 } 322 } 323 324 /** 325 * 后序遍历递归解法 326 * （1）如果二叉树为空，空操作 327 * （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 328 */ 329 public static void postorderTraversalRec(TreeNode root) { 330 if (root == null) { 331 return; 332 } 333 postorderTraversalRec(root.left); 334 postorderTraversalRec(root.right); 335 System.out.print(root.val + " "); 336 } 337 338 /** 339 * 后序遍历迭代解法 340 * http://www.youtube.com/watch?v=hv-mJUs5mvU 341 * 342 */ 343 public static void postorderTraversal(TreeNode root) { 344 if (root == null) { 345 return; 346 } 347 348 Stack<TreeNode> s = new Stack<TreeNode>(); // 第一个stack用于添加node和它的左右孩子 349 Stack<TreeNode> output = new Stack<TreeNode>();// 第二个stack用于翻转第一个stack输出 350 351 s.push(root); 352 while( !s.isEmpty() ){ // 确保所有元素都被翻转转移到第二个stack 353 TreeNode cur = s.pop(); // 把栈顶元素添加到第二个stack 354 output.push(cur); 355 356 if(cur.left != null){ // 把栈顶元素的左孩子和右孩子分别添加入第一个stack 357 s.push(cur.left); 358 } 359 if(cur.right != null){ 360 s.push(cur.right); 361 } 362 } 363 364 while( !output.isEmpty() ){ // 遍历输出第二个stack，即为后序遍历 365 System.out.print(output.pop().val + " "); 366 } 367 } 368 369 /** 370 * 分层遍历二叉树（按层次从上往下，从左往右）迭代 371 * 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点 372 * ，访问，若左子节点或右子节点不为空，将其压入队列 373 */ 374 public static void levelTraversal(TreeNode root) { 375 if (root == null) { 376 return; 377 } 378 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 379 queue.push(root); 380 381 while (!queue.isEmpty()) { 382 TreeNode cur = queue.removeFirst(); 383 System.out.print(cur.val + " "); 384 if (cur.left != null) { 385 queue.add(cur.left); 386 } 387 if (cur.right != null) { 388 queue.add(cur.right); 389 } 390 } 391 } 392 393 /** 394 * 分层遍历二叉树（递归） 395 * 很少有人会用递归去做level traversal 396 * 基本思想是用一个大的ArrayList，里面包含了每一层的ArrayList。 397 * 大的ArrayList的size和level有关系 398 * 399 * 这是我目前见到的最好的递归解法！ 400 * http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal#answer-container-2543 401 */ 402 public static void levelTraversalRec(TreeNode root) { 403 ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>(); 404 dfs(root, 0, ret); 405 System.out.println(ret); 406 } 407 408 private static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret){ 409 if(root == null){ 410 return; 411 } 412 413 // 添加一个新的ArrayList表示新的一层 414 if(level >= ret.size()){ 415 ret.add(new ArrayList<Integer>()); 416 } 417 418 ret.get(level).add(root.val); // 把节点添加到表示那一层的ArrayList里 419 dfs(root.left, level+1, ret); // 递归处理下一层的左子树和右子树 420 dfs(root.right, level+1, ret); 421 } 422 423 424 /** 425 * 将二叉查找树变为有序的双向链表 要求不能创建新节点，只调整指针。 426 * 递归解法： 427 * 参考了http://*.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016 428 * 感觉是最清晰的递归解法，但要注意递归完，root会在链表的中间位置，因此要手动 429 * 把root移到链表头或链表尾 430 */ 431 public static TreeNode convertBST2DLLRec(TreeNode root) { 432 root = convertBST2DLLSubRec(root); 433 434 // root会在链表的中间位置，因此要手动把root移到链表头 435 while(root.left != null){ 436 root = root.left; 437 } 438 return root; 439 } 440 441 /** 442 * 递归转换BST为双向链表(DLL) 443 */ 444 public static TreeNode convertBST2DLLSubRec(TreeNode root){ 445 if(root==null || (root.left==null && root.right==null)){ 446 return root; 447 } 448 449 TreeNode tmp = null; 450 if(root.left != null){ // 处理左子树 451 tmp = convertBST2DLLSubRec(root.left); 452 while(tmp.right != null){ // 寻找最右节点 453 tmp = tmp.right; 454 } 455 tmp.right = root; // 把左子树处理后结果和root连接 456 root.left = tmp; 457 } 458 if(root.right != null){ // 处理右子树 459 tmp = convertBST2DLLSubRec(root.right); 460 while(tmp.left != null){ // 寻找最左节点 461 tmp = tmp.left; 462 } 463 tmp.left = root; // 把右子树处理后结果和root连接 464 root.right = tmp; 465 } 466 return root; 467 } 468 469 /** 470 * 将二叉查找树变为有序的双向链表 迭代解法 471 // * 类似inorder traversal的做法 472 */ 473 public static TreeNode convertBST2DLL(TreeNode root) { 474 if(root == null){ 475 return null; 476 } 477 Stack<TreeNode> stack = new Stack<TreeNode>(); 478 TreeNode cur = root; // 指向当前处理节点 479 TreeNode old = null; // 指向前一个处理的节点 480 TreeNode head = null; // 链表头 481 482 while( true ){ 483 while(cur != null){ // 先添加一个非空节点所有的左孩子到栈 484 stack.push(cur); 485 cur = cur.left; 486 } 487 488 if(stack.isEmpty()){ 489 break; 490 } 491 492 // 因为此时已经没有左孩子了，所以输出栈顶元素 493 cur = stack.pop(); 494 if(old != null){ 495 old.right = cur; 496 } 497 if(head == null){ // /第一个节点为双向链表头节点 498 head = cur; 499 } 500 501 old = cur; // 更新old 502 cur = cur.right; // 准备处理右子树 503 } 504 505 return head; 506 } 507 508 /** 509 * 求二叉树第K层的节点个数 递归解法： 510 * （1）如果二叉树为空或者k<1返回0 511 * （2）如果二叉树不为空并且k==1，返回1 512 * （3）如果二叉树不为空且k>1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和 513 * 514 * 求以root为根的k层节点数目 等价于 求以root左孩子为根的k-1层（因为少了root那一层）节点数目 加上 515 * 以root右孩子为根的k-1层（因为少了root那一层）节点数目 516 * 517 * 所以遇到树，先把它拆成左子树和右子树，把问题降解 518 * 519 */ 520 public static int getNodeNumKthLevelRec(TreeNode root, int k) { 521 if (root == null || k < 1) { 522 return 0; 523 } 524 525 if (k == 1) { 526 return 1; 527 } 528 int numLeft = getNodeNumKthLevelRec(root.left, k - 1); // 求root左子树的k-1层节点数 529 int numRight = getNodeNumKthLevelRec(root.right, k - 1); // 求root右子树的k-1层节点数 530 return numLeft + numRight; 531 } 532 533 /** 534 * 求二叉树第K层的节点个数 迭代解法： 535 * 同getDepth的迭代解法 536 */ 537 public static int getNodeNumKthLevel(TreeNode root, int k){ 538 if(root == null){ 539 return 0; 540 } 541 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 542 queue.add(root); 543 544 int i = 1; 545 int currentLevelNodes = 1; // 当前Level，node的数量 546 int nextLevelNodes = 0; // 下一层Level，node的数量 547 548 while( !queue.isEmpty() && i<k){ 549 TreeNode cur = queue.remove(); // 从队头位置移除 550 currentLevelNodes--; // 减少当前Level node的数量 551 if(cur.left != null){ // 如果有左孩子，加到队尾 552 queue.add(cur.left); 553 nextLevelNodes++; // 并增加下一层Level node的数量 554 } 555 if(cur.right != null){ // 如果有右孩子，加到队尾 556 queue.add(cur.right); 557 nextLevelNodes++; 558 } 559 560 if(currentLevelNodes == 0){ // 说明已经遍历完当前层的所有节点 561 currentLevelNodes = nextLevelNodes; // 初始化下一层的遍历 562 nextLevelNodes = 0; 563 i++; // 进入到下一层 564 } 565 } 566 567 return currentLevelNodes; 568 } 569 570 /** 571 * 求二叉树中叶子节点的个数（递归） 572 */ 573 public static int getNodeNumLeafRec(TreeNode root) { 574 // 当root不存在，返回空 575 if (root == null) { 576 return 0; 577 } 578 579 // 当为叶子节点时返回1 580 if (root.left == null && root.right == null) { 581 return 1; 582 } 583 584 // 把一个树拆成左子树和右子树之和，原理同上一题 585 return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right); 586 } 587 588 /** 589 * 求二叉树中叶子节点的个数（迭代） 590 * 还是基于Level order traversal 591 */ 592 public static int getNodeNumLeaf(TreeNode root) { 593 if(root == null){ 594 return 0; 595 } 596 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 597 queue.add(root); 598 599 int leafNodes = 0; // 记录上一个Level，node的数量 600 601 while( !queue.isEmpty() ){ 602 TreeNode cur = queue.remove(); // 从队头位置移除 603 if(cur.left != null){ // 如果有左孩子，加到队尾 604 queue.add(cur.left); 605 } 606 if(cur.right != null){ // 如果有右孩子，加到队尾 607 queue.add(cur.right); 608 } 609 if(cur.left==null && cur.right==null){ // 叶子节点 610 leafNodes++; 611 } 612 } 613 614 return leafNodes; 615 } 616 617 /** 618 * 判断两棵二叉树是否相同的树。 619 * 递归解法： 620 * （1）如果两棵二叉树都为空，返回真 621 * （2）如果两棵二叉树一棵为空，另一棵不为空，返回假 622 * （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假 623 */ 624 public static boolean isSameRec(TreeNode r1, TreeNode r2) { 625 // 如果两棵二叉树都为空，返回真 626 if (r1 == null && r2 == null) { 627 return true; 628 } 629 // 如果两棵二叉树一棵为空，另一棵不为空，返回假 630 else if (r1 == null || r2 == null) { 631 return false; 632 } 633 634 if(r1.val != r2.val){ 635 return false; 636 } 637 boolean leftRes = isSameRec(r1.left, r2.left); // 比较对应左子树 638 boolean rightRes = isSameRec(r1.right, r2.right); // 比较对应右子树 639 return leftRes && rightRes; 640 } 641 642 /** 643 * 判断两棵二叉树是否相同的树（迭代） 644 * 遍历一遍即可，这里用preorder 645 */ 646 public static boolean isSame(TreeNode r1, TreeNode r2) { 647 // 如果两个树都是空树，则返回true 648 if(r1==null && r2==null){ 649 return true; 650 } 651 652 // 如果有一棵树是空树，另一颗不是，则返回false 653 if(r1==null || r2==null){ 654 return false; 655 } 656 657 Stack<TreeNode> s1 = new Stack<TreeNode>(); 658 Stack<TreeNode> s2 = new Stack<TreeNode>(); 659 660 s1.push(r1); 661 s2.push(r2); 662 663 while(!s1.isEmpty() && !s2.isEmpty()){ 664 TreeNode n1 = s1.pop(); 665 TreeNode n2 = s2.pop(); 666 if(n1==null && n2==null){ 667 continue; 668 }else if(n1!=null && n2!=null && n1.val==n2.val){ 669 s1.push(n1.right); 670 s1.push(n1.left); 671 s2.push(n2.right); 672 s2.push(n2.left); 673 }else{ 674 return false; 675 } 676 } 677 return true; 678 } 679 680 /** 681 * 判断二叉树是不是平衡二叉树 递归解法： 682 * （1）如果二叉树为空，返回真 683 * （2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假 684 */ 685 public static boolean isAVLRec(TreeNode root) { 686 if(root == null){ // 如果二叉树为空，返回真 687 return true; 688 } 689 690 // 如果左子树和右子树高度相差大于1，则非平衡二叉树, getDepthRec()是前面实现过的求树高度的方法 691 if(Math.abs(getDepthRec(root.left) - getDepthRec(root.right)) > 1){ 692 return false; 693 } 694 695 // 递归判断左子树和右子树是否为平衡二叉树 696 return isAVLRec(root.left) && isAVLRec(root.right); 697 } 698 699 700 /** 701 * 求二叉树的镜像 递归解法： 702 * （1）如果二叉树为空，返回空 703 * （2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树 704 */ 705 // 1. 破坏原来的树，把原来的树改成其镜像 706 public static TreeNode mirrorRec(TreeNode root) { 707 if (root == null) { 708 return null; 709 } 710 711 TreeNode left = mirrorRec(root.left); 712 TreeNode right = mirrorRec(root.right); 713 714 root.left = right; 715 root.right = left; 716 return root; 717 } 718 719 // 2. 不能破坏原来的树，返回一个新的镜像树 720 public static TreeNode mirrorCopyRec(TreeNode root){ 721 if(root == null){ 722 return null; 723 } 724 725 TreeNode newNode = new TreeNode(root.val); 726 newNode.left = mirrorCopyRec(root.right); 727 newNode.right = mirrorCopyRec(root.left); 728 729 return newNode; 730 } 731 732 // 3. 判断两个树是否互相镜像 733 public static boolean isMirrorRec(TreeNode r1, TreeNode r2){ 734 // 如果两个树都是空树，则返回true 735 if(r1==null && r2==null){ 736 return true; 737 } 738 739 // 如果有一棵树是空树，另一颗不是，则返回false 740 if(r1==null || r2==null){ 741 return false; 742 } 743 744 // 如果两个树都非空树，则先比较根节点 745 if(r1.val != r2.val){ 746 return false; 747 } 748 749 // 递归比较r1的左子树的镜像是不是r2右子树 和 750 // r1的右子树的镜像是不是r2左子树 751 return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left); 752 } 753 754 // 1. 破坏原来的树，把原来的树改成其镜像 755 public static void mirror(TreeNode root) { 756 if(root == null){ 757 return; 758 } 759 760 Stack<TreeNode> stack = new Stack<TreeNode>(); 761 stack.push(root); 762 while( !stack.isEmpty() ){ 763 TreeNode cur = stack.pop(); 764 765 // 交换左右孩子 766 TreeNode tmp = cur.right; 767 cur.right = cur.left; 768 cur.left = tmp; 769 770 if(cur.right != null){ 771 stack.push(cur.right); 772 } 773 if(cur.left != null){ 774 stack.push(cur.left); 775 } 776 } 777 } 778 779 // 2. 不能破坏原来的树，返回一个新的镜像树 780 public static TreeNode mirrorCopy(TreeNode root){ 781 if(root == null){ 782 return null; 783 } 784 785 Stack<TreeNode> stack = new Stack<TreeNode>(); 786 Stack<TreeNode> newStack = new Stack<TreeNode>(); 787 stack.push(root); 788 TreeNode newRoot = new TreeNode(root.val); 789 newStack.push(newRoot); 790 791 while( !stack.isEmpty() ){ 792 TreeNode cur = stack.pop(); 793 TreeNode newCur = newStack.pop(); 794 795 if(cur.right != null){ 796 stack.push(cur.right); 797 newCur.left = new TreeNode(cur.right.val); 798 newStack.push(newCur.left); 799 } 800 if(cur.left != null){ 801 stack.push(cur.left); 802 newCur.right = new TreeNode(cur.left.val); 803 newStack.push(newCur.right); 804 } 805 } 806 807 return newRoot; 808 } 809 810 811 /** 812 * 求二叉树中两个节点的最低公共祖先节点 813 * 递归解法： 814 * （1）如果两个节点分别在根节点的左子树和右子树，则返回根节点 815 * （2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树 816 */ 817 public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) { 818 if (findNodeRec(root.left, n1)) { // 如果n1在树的左子树 819 if (findNodeRec(root.right, n2)) { // 如果n2在树的右子树 820 return root; // 返回根节点 821 } else { // 如果n2也在树的左子树 822 return getLastCommonParentRec(root.left, n1, n2); // 递归处理 823 } 824 } else { // 如果n1在树的右子树 825 if (findNodeRec(root.left, n2)) { // 如果n2在左子树 826 return root; 827 } else { // 如果n2在右子树 828 return getLastCommonParentRec(root.right, n1, n2); // 递归处理 829 } 830 } 831 } 832 833 // 帮助方法，递归判断一个点是否在树里 834 private static boolean findNodeRec(TreeNode root, TreeNode node) { 835 if (root == null || node == null) { 836 return false; 837 } 838 if (root == node) { 839 return true; 840 } 841 842 // 先尝试在左子树中查找 843 boolean found = findNodeRec(root.left, node); 844 if (!found) { // 如果查找不到，再在右子树中查找 845 found = findNodeRec(root.right, node); 846 } 847 return found; 848 } 849 850 // 求二叉树中两个节点的最低公共祖先节点 （更加简洁版的递归） 851 public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) { 852 if(root == null){ 853 return null; 854 } 855 856 // 如果有一个match，则说明当前node就是要找的最低公共祖先 857 if(root.equals(n1) || root.equals(n2)){ 858 return root; 859 } 860 TreeNode commonInLeft = getLastCommonParentRec2(root.left, n1, n2); 861 TreeNode commonInRight = getLastCommonParentRec2(root.right, n1, n2); 862 863 // 如果一个左子树找到，一个在右子树找到，则说明root是唯一可能的最低公共祖先 864 if(commonInLeft!=null && commonInRight!=null){ 865 return root; 866 } 867 868 // 其他情况是要不然在左子树要不然在右子树 869 if(commonInLeft != null){ 870 return commonInLeft; 871 } 872 873 return commonInRight; 874 } 875 876 /** 877 * 非递归解法： 878 * 先求从根节点到两个节点的路径，然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点 879 */ 880 public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) { 881 if (root == null || n1 == null || n2 == null) { 882 return null; 883 } 884 885 ArrayList<TreeNode> p1 = new ArrayList<TreeNode>(); 886 boolean res1 = getNodePath(root, n1, p1); 887 ArrayList<TreeNode> p2 = new ArrayList<TreeNode>(); 888 boolean res2 = getNodePath(root, n2, p2); 889 890 if (!res1 || !res2) { 891 return null; 892 } 893 894 TreeNode last = null; 895 Iterator<TreeNode> iter1 = p1.iterator(); 896 Iterator<TreeNode> iter2 = p2.iterator(); 897 898 while (iter1.hasNext() && iter2.hasNext()) { 899 TreeNode tmp1 = iter1.next(); 900 TreeNode tmp2 = iter2.next(); 901 if (tmp1 == tmp2) { 902 last = tmp1; 903 } else { // 直到遇到非公共节点 904 break; 905 } 906 } 907 return last; 908 } 909 910 // 把从根节点到node路径上所有的点都添加到path中 911 private static boolean getNodePath(TreeNode root, TreeNode node, ArrayList<TreeNode> path) { 912 if (root == null) { 913 return false; 914 } 915 916 path.add(root); // 把这个节点加到路径中 917 if (root == node) { 918 return true; 919 } 920 921 boolean found = false; 922 found = getNodePath(root.left, node, path); // 先在左子树中找 923 924 if (!found) { // 如果没找到，再在右子树找 925 found = getNodePath(root.right, node, path); 926 } 927 if (!found) { // 如果实在没找到证明这个节点不在路径中，说明刚才添加进去的不是路径上的节点，删掉！ 928 path.remove(root); 929 } 930 931 return found; 932 } 933 934 /** 935 * 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter) 936 * 递归解法： 937 * （1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0 938 * （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离， 939 * 要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离， 940 * 同时记录左子树和右子树节点中到根节点的最大距离。 941 * 942 * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html 943 * 944 * 计算一个二叉树的最大距离有两个情况: 945 946 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。 947 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。 948 只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离 949 */ 950 public static Result getMaxDistanceRec(TreeNode root){ 951 if(root == null){ 952 Result empty = new Result(0, -1); // 目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0 953 return empty; 954 } 955 956 // 计算出左右子树分别最大距离 957 Result lmd = getMaxDistanceRec(root.left); 958 Result rmd = getMaxDistanceRec(root.right); 959 960 Result res = new Result(); 961 res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1; // 当前最大深度 962 // 取情况A和情况B中较大值 963 res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) ); 964 return res; 965 } 966 967 private static class Result{ 968 int maxDistance; 969 int maxDepth; 970 public Result() { 971 } 972 973 public Result(int maxDistance, int maxDepth) { 974 this.maxDistance = maxDistance; 975 this.maxDepth = maxDepth; 976 } 977 } 978 979 /** 980 * 13. 由前序遍历序列和中序遍历序列重建二叉树（递归） 981 * 感觉这篇是讲的最为清晰的: 982 * http://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals/ 983 * 文中还提到一种避免开额外空间的方法，等下次补上 984 */ 985 public static TreeNode rebuildBinaryTreeRec(List<Integer> preOrder, List<Integer> inOrder){ 986 TreeNode root = null; 987 List<Integer> leftPreOrder; 988 List<Integer> rightPreOrder; 989 List<Integer> leftInorder; 990 List<Integer> rightInorder; 991 int inorderPos; 992 int preorderPos; 993 994 if ((preOrder.size() != 0) && (inOrder.size() != 0)) 995 { 996 // 把preorder的第一个元素作为root 997 root = new TreeNode(preOrder.get(0)); 998 999 // Based upon the current node data seperate the traversals into leftPreorder, rightPreorder, 1000 // leftInorder, rightInorder lists 1001 // 因为知道root节点了，所以根据root节点位置，把preorder，inorder分别划分为 root左侧 和 右侧 的两个子区间 1002 inorderPos = inOrder.indexOf(preOrder.get(0)); // inorder序列的分割点 1003 leftInorder = inOrder.subList(0, inorderPos); 1004 rightInorder = inOrder.subList(inorderPos + 1, inOrder.size()); 1005 1006 preorderPos = leftInorder.size(); // preorder序列的分割点 1007 leftPreOrder = preOrder.subList(1, preorderPos + 1); 1008 rightPreOrder = preOrder.subList(preorderPos + 1, preOrder.size()); 1009 1010 root.left = rebuildBinaryTreeRec(leftPreOrder, leftInorder); // root的左子树就是preorder和inorder的左侧区间而形成的树 1011 root.right = rebuildBinaryTreeRec(rightPreOrder, rightInorder); // root的右子树就是preorder和inorder的右侧区间而形成的树 1012 } 1013 1014 return root; 1015 } 1016 1017 /** 1018 14. 判断二叉树是不是完全二叉树（迭代） 1019 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数， 1020 第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 1021 有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时， 1022 则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。 1023 */ 1024 public static boolean isCompleteBinaryTree(TreeNode root){ 1025 if(root == null){ 1026 return false; 1027 } 1028 1029 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 1030 queue.add(root); 1031 boolean mustHaveNoChild = false; 1032 boolean result = true; 1033 1034 while( !queue.isEmpty() ){ 1035 TreeNode cur = queue.remove(); 1036 if(mustHaveNoChild){ // 已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空） 1037 if(cur.left!=null || cur.right!=null){ 1038 result = false; 1039 break; 1040 } 1041 } else { 1042 if(cur.left!=null && cur.right!=null){ // 如果左子树和右子树都非空，则继续遍历 1043 queue.add(cur.left); 1044 queue.add(cur.right); 1045 }else if(cur.left!=null && cur.right==null){ // 如果左子树非空但右子树为空，说明已经出现空节点，之后必须都为空子树 1046 mustHaveNoChild = true; 1047 queue.add(cur.left); 1048 }else if(cur.left==null && cur.right!=null){ // 如果左子树为空但右子树非空，说明这棵树已经不是完全二叉完全树！ 1049 result = false; 1050 break; 1051 }else{ // 如果左右子树都为空，则后面的必须也都为空子树 1052 mustHaveNoChild = true; 1053 } 1054 } 1055 } 1056 return result; 1057 } 1058 1059 /** 1060 * 14. 判断二叉树是不是完全二叉树（递归） 1061 * http://*.com/questions/1442674/how-to-determine-whether-a-binary-tree-is-complete 1062 * 1063 */ 1064 public static boolean isCompleteBinaryTreeRec(TreeNode root){ 1065 // Pair notComplete = new Pair(-1, false); 1066 // return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete); 1067 return isCompleteBinaryTreeSubRec(root).height != -1; 1068 } 1069 1070 // 递归判断是否满树（完美） 1071 public static boolean isPerfectBinaryTreeRec(TreeNode root){ 1072 return isCompleteBinaryTreeSubRec(root).isFull; 1073 } 1074 1075 // 递归，要创建一个Pair class来保存树的高度和是否已满的信息 1076 public static Pair isCompleteBinaryTreeSubRec(TreeNode root){ 1077 if(root == null){ 1078 return new Pair(0, true); 1079 } 1080 1081 Pair left = isCompleteBinaryTreeSubRec(root.left); 1082 Pair right = isCompleteBinaryTreeSubRec(root.right); 1083 1084 // 左树满节点，而且左右树相同高度，则是唯一可能形成满树（若右树也是满节点）的情况 1085 if(left.isFull && left.height==right.height){ 1086 return new Pair(1+left.height, right.isFull); 1087 } 1088 1089 // 左树非满，但右树是满节点，且左树高度比右树高一 1090 // 注意到如果其左树为非完全树，则它的高度已经被设置成-1， 1091 // 因此不可能满足第二个条件！ 1092 if(right.isFull && left.height==right.height+1){ 1093 return new Pair(1+left.height, false); 1094 } 1095 1096 // 其他情况都是非完全树，直接设置高度为-1 1097 return new Pair(-1, false); 1098 } 1099 1100 private static class Pair{ 1101 int height; // 树的高度 1102 boolean isFull; // 是否是个满树 1103 1104 public Pair(int height, boolean isFull) { 1105 this.height = height; 1106 this.isFull = isFull; 1107 } 1108 1109 public boolean equalsTo(Pair obj){ 1110 return this.height==obj.height && this.isFull==obj.isFull; 1111 } 1112 } 1113 1114 }
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
（1）它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，
（2）并且左右两个子树都是一棵平衡二叉树。
二叉树的镜像：先序遍历树的每个结点，若遍历到的结点有子结点，则交换它的两个子结点
完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
意的一个二叉树，都可以补成一个满二叉树。这样中间就会有很多空洞。在广度优先遍历的时候，如果是满二叉树，或者完全二叉树，这些空洞是在广度优先的遍历的末尾，所以，但我们遍历到空洞的时候，整个二叉树就已经遍历完成了。而如果，是非完全二叉树，
我们遍历到空洞的时候，就会发现，空洞后面还有没有遍历到的值。这样，只要根据是否遍历到空洞，整个树的遍历是否结束来判断是否是完全的二叉树。