給定一個二叉樹和其中的一個節點,如何找出中序遍歷序列的下一個節點?樹中的節點除了左右子節點外,還包含父節點。
**規則**
輸入: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);
}
```