Special topic of binary tree -- acwing 19 The next node of the binary tree (find the successor of the node in the tree)

The question ：

Find the successor of a given node in a binary tree .

Time complexity ：

( simulation ) O(h)

Ideas ：

Just discuss the situation , As shown in the figure below ：

• If the current node has a right son , Then the leftmost node in the right subtree is the successor of the current node . such as F The successor is H;
• If the current node has no right son , You need to follow father The domain keeps looking up , The first one to find is its father Left son's node , Of this node father It is the successor of the current node . For example, the current node is D, Then the first satisfaction is its father The node of the left son is C, be C Of father Namely D In the subsequent , namely F yes D In the subsequent .
  

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
		if (p->right)
		{
			p = p->right;
			while (p->left)
			{
				p = p->left;
			}
			return p;
		}
		while (p->father && p == p->father->right) p = p->father;
		return p->father;
    }
};