题目链接

牛客网

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

  1. struct TreeLinkNode {
  2.     int val;
  3.     struct TreeLinkNode *left;
  4.     struct TreeLinkNode *right;
  5.     struct TreeLinkNode *next;//父节点
  6.     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
  8.     }
  9. };

解题思路

8. 二叉树的下一个结点 - 图1
① 如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点；

8. 二叉树的下一个结点 - 图2
② 否则，向上找第一个左链接指向的树包含该节点的祖先节点。
8. 二叉树的下一个结点 - 图3

  1. class Solution {
  2. public:
  3.     TreeLinkNode* GetNext(TreeLinkNode* pNode)
  4.     {
  5.         if(!pNode)//当结点是空时,返回null
  6.             return NULL;
  7.         if(pNode->right)//当该结点有右子树，求右子树最左边的结点
  8.         {
  9.             pNode = pNode->right;
  10.             while(pNode->left)
  11.             {
  12.                 pNode = pNode->left;
  13.             }
  14.             return pNode;
  15.         }
  16.         while(pNode->next)//当该结点没有右子树时,向上找第一个左链接指向的树包含该结点的祖先结点
  17.         {
  18.             if(pNode->next->left==pNode)
  19.                 return pNode->next;
  20.             pNode = pNode->next;
  21.         }
  22.         return NULL;//当该结点是二叉树最右边的结点时，返回空
  23.     }
  24. };
  • 时间复杂度：最坏情况下为O(N)
  • 空间复杂度：O(1)