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

二叉树的下一个结点：最直观的想法是，首先保存给定结点所对应的值pval，然后利用next指针找到二叉树的根节点Node，再使用双指针法与递归进行中序遍历，当前驱指针pre指向pval所对应的结点时，则使用result记录所求结果，其指向的即为二叉树的下一个结点。如果dfs设置返回值反而不太方便，所以将pre和result作为参数传递给函数，但是由于指针变量也是变量，又需要在函数内部更改这两个变量的值，故使用这两个变量的引用。

void dfs(TreeLinkNode* root, int pval, TreeLinkNode* &pre,TreeLinkNode*& result) 
{
   if (root == nullptr) return;
   dfs(root->left, pval, pre, result); //左
   if (pre && pre->val == pval) //中
   result = root;
   pre = root;
   dfs(root->right, pval, pre, result); //右
}
TreeLinkNode* GetNext(TreeLinkNode* pNode) //pNode指向的是待找节点
{ 
   int pval = pNode->val;
   TreeLinkNode* Node = pNode;
   while (Node->next) //寻找根节点
     Node = Node->next;
   TreeLinkNode* pre = nullptr;
   TreeLinkNode* result=nullptr;
   dfs(Node, pval, pre, result);
   return result;
}

优化：上述中序遍历是遍历了整个二叉树，我们可以利用中序遍历中当前结点的下一个结点的规律，即如果当前结点的右子树不为空，那么下一个结点是右子树的最左下，反之如果当前结点的右子树为空，那么下一个结点是当前结点的第一个右父结点，前者可以使用循环实现，后者可以使用双指针实现。

TreeLinkNode* GetNext(TreeLinkNode* pNode) 
{
   TreeLinkNode *p=pNode->right;
   TreeLinkNode *q=NULL,*r=NULL;
   if(p!=NULL) //右子树不为空则下一个节点为右子树的最左下
   {
      while(p&&p->left)
      p=p->left;
      return p;
   }
   else //右子树为空则下一个节点为第一个右父节点
   {
      q=pNode->next;
      r=pNode;
      while(q&&q->right==r)
      {
        r=q;
        q=q->next;
      }
      return q;
    }
      return NULL;
}

最后补充：一般二叉树类型的题目中都是给定参数为二叉树的根结点，但是可能代码接口中的输入看着很迷糊，其意思是pNode是给定的当前结点，这是整个完整的二叉树的一部分，我们可以根据该结点找到二叉树的根结点。