1.查询后继节点后继节点：中序遍历时，一个节点的下一个节点就是该节点的后继节点。指定二叉树的结构如下：publicstaticclassNode{publicintvalue;公共节点离开；公共节点权；//父节点publicNodeparent;公共节点(intv){值=v;}}如何快速找到一个Node的后继节点一、思路1、根据后继节点的定义找到一个节点的后继节点，即依次遍历二叉树，然后找到指定的后继节点节点。时间复杂度为O(N)。显然这种方法不是最优解。2.根据二叉树的结构和多个父指针查找(1)如果指定节点X有右树，则X的后继节点是X右树上的最左子节点。由定义导出的后继节点。(2)X没有右树，则根据父节点向上查找，直到找到一个节点是其父节点Y的左孩子，则Y为X的后继节点；如果一路向上都没有找到结点，则它是其父结点的左孩子，则该结点是最右孩子，没有后继结点。为什么：因为X是Y的左树上最右边的孩子，按照中序遍历的顺序，遍历完X之后就是Y。时间复杂度为O(K)（K是从指定的最短节点数节点到后继节点）。显然，第二种方法更好。2.代码/***寻找后继节点**@authorJava与算法学习：周一*/publicstaticNodesuccessorNode(Nodenode){if(node==null){returnnull;}//有一个右孩子if(node.right!=null){//在右树上找到最左边的孩子returngetMaxLeft(node.right);}else{//没有右孩子//根据父指针查找Nodeparent=node.parent;//如果没有找到top，且当前节点是父节点的右孩子，继续向上查找while(parent!=null&&parent.right==node){node=parent;父节点=节点父节点；}//parent包含两种情况//1）找到顶层，即parent为null//2）找到一个节点，它是父节点的左孩子returnparent;}}/***获取节点最左边的子节点*/privatestaticNodegetMaxLeft(Noderight){if(right==null){returnnull;}while(right.left!=null){right=right.left;}returnreturnright;}Question这是微软以前问的一道面试题。这道题真的很考验一个人的能力，不是难，而是考验对算法的掌握能力。1.题目描述：请将一张纸条竖放在桌子上，然后将纸条从下往上对折一次，压出折痕展开。此时折痕呈凹形（下折痕），即折痕突出的方向指向纸条背面。如果将纸条从下往上连续对折两次，压出折痕后再展开，此时有三个折痕，从上到下分别是下折痕、下折痕和上折痕底部。给定一个输入参数N，表示将纸条从下往上连续对折N次。请从上到下打印所有折痕的方向。例如：当N=1时，打印：down（凹）；当N=2时，打印：down（凹），down（凹），up（凸）2.多次折叠后，你会发现：下一个折痕最后一次，总是向上凹，向下凸。即第二个折痕在第一个凹陷（1凹）的上方凹进（2凹），在下方凸起（2凸）；第三条折痕在2凹上方3凹，底部3凸，2凸顶部3凹，底部3凸；等等。然后依次展开，放在二叉树上。令人惊讶的是，从上到下打印所有折痕的方向是二叉树的中序遍历。3.代码/***@authorJava与算法学习：星期一*/publicstaticvoidpaperFolding(intn){//二叉树头节点是凹process(1,n,true);}/***@parami节点的层数*@paramn一共多少层*@paramdowntrue=concave,false=convex*/privatestaticvoidprocess(inti,intn,booleandown){if(i>n){返回;}//顶部是凹形过程(i+1,n,true);System.out.print(down?"凹":"凸");//最下面是凸过程(i+1,n,false);}你有没有发现，一旦有了正确的想法，就会豁然开朗，掌握也是一种能力。本文代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/SuccessorNode.java
