Inorder 1.png
Inorder 2.png
解題思路 ：
先解決 root == nullptr 的問題 直接回傳 root
之後判斷兩種狀況
p 點有 right child:
這種情形 inorder 的下一個 successor 必須是 right child 子樹的最小值 ( 最左下層 )p 點沒有 right child:
此時要檢查是否有 parent 並且此 parent 的值要比 p 大 ( 這樣 p 才會是 parent 的 left child ) 在 inorder 中如果 p 為 left child 那 parent 就會是下一個出列
C++ code :
<pre><code>
TreeNode* findMin(TreeNode* p)
{
while(p->left != nullptr)
{
p = p->left;
}
return p;
}
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
// write your code here
if(root == nullptr) return root;
//target has a right child
if(p->right != nullptr) return findMin(p->right);
//target has no right child
TreeNode *parent = nullptr;
TreeNode *tmp = root;
while(tmp != p)
{
if(p->val < tmp->val)
{
parent = tmp;
tmp = tmp->left;
}
else tmp = tmp->right;
}
return parent;
}
};
