题解 | #二叉树的下一个结点#

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
  public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
      if (pNode->right) {
      //  当前结点有右子树，则寻找其右子树中最左叶子结点
        TreeLinkNode *cur = pNode->right;
        
        while (cur->left) {
          cur = cur->left;
        }
        
        return cur;
      } else if (pNode->next) {
      //  没有右子树则向上追溯
        TreeLinkNode *cur = pNode;
        
      //  追溯到结点为父节点的左子树，则该父节点为下一位遍历
        while (cur->next && cur != cur->next->left) {
          cur = cur->next;
        }
        
        if (cur->next) {
          return cur->next;
        } 
        
      //  遍历到根节点仍然找不到，则该结点是最后一个遍历结点
      //  右子树的最右结点
        return nullptr;
      }
      
      return nullptr;
    }
};