二叉树的下一个节点（非递归）

• 当前节点不存在右子树，且该节点为父节点的右孩子，递归一样找父节点的中序遍历的下一个节点。
  满足这样的条件就是该节点为父节点的右孩子。

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (!pNode) {
            return pNode;
        }

        // 当前节点有右子树 下一个节点是右子树中序遍历的第一个节点，即下一个节点就是右孩子的最左孩子结点。
        if (pNode->right) {
            pNode = pNode->right;
            while (pNode->left) {
                pNode = pNode->left;
            }
            return pNode;
        }

        // 当前节点不存在右子树，且该节点为父节点的右孩子，递归一样找父节点的中序遍历的下一个节点。满足这样的条件就是该节点为父节点的右孩子。
        // 当前节点不存在右子树，且该节点为父节点的左孩子，直接就是其父亲节点。
        while (pNode->next) {
            TreeLinkNode *root = pNode->next;
            if (root->left == pNode) {
                return root;
            }
            pNode = pNode->next;
        }

        return nullptr;
    }
};