給定一個二叉樹和其中的一個節點，如何找出中序遍歷序列的下一個節點？樹中的節點除了左右子節點外，還包含父節點。 **規則** 輸入：TreeNode node 輸出：下一個節點TreeNode node case： ``` 節點為null 獲得中序遍歷的下一個節點 節點有兩個要考慮的因素: 1.node是其父節點的左節點還是右節點 2.node是否有左右節點， 左/右 無左無右 有左無右 無左有右 有左有右 左 左1 左2 左3 左4 右 右1 右2 右3 右4 ``` **思路** 對上面的幾種情況進行統計， 左-無左無右：父節點 左-有左無右：父節點 左-無左有右：右子樹的最左節點 左-有左有右：右子樹的最左節點 右-無左無右：沿著父節點一直往上找，直到找到一個節點是其父的左節點 右-有左無右：沿著父節點一直往上找，直到找到一個節點是其父的左節點 右-無左有右：右子樹的最左節點 右-有左有右：右子樹的最左節點 綜合上面的情況，如果節點node有右節點，則查找右子樹的最左邊的節點；如果沒有右節點，那么綜合一下可以總結為，從node出發，向上查找，直到找到一個節點是其父的左節點 ，由于node位于左節點時，會立即找到，因此返回的是父節點。 **代碼** ``` public TreeNode getNext(TreeNode node) { if(node == null) { return null; } if(node.right != null) { // node有右子樹 return getLeft(node.right); }else { // node右子樹為null if(node.parent == null) { return null; } /********************************************** if(node == node.parent.left) { // 左節點 return node.parent; }else if(node == node.parent.right) { // 右節點 TreeNode tmp = node.parent; while(tmp.parent != null && tmp.parent.right == tmp) { tmp = tmp.parent; } return tmp.parent; }***************************************************/ TreeNode tmp = node; while(tmp.parent != null && tmp.parent.right == tmp) { tmp = tmp.parent; } return tmp.parent; } } private TreeNode getLeft(TreeNode tree) { if(tree.left == null) return tree; return getLeft(tree.left); } ```