CodeTop：补充题 12. 二叉树的下一个结点
牛客网：[编程题]二叉树的下一个结点

题目

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

示例：
补充题 12. 二叉树的下一个结点 - 图1

  1. 输入：{8,6,10,5,7,9,11},8
  2. 输出：9
  1. 输入：{8,6,10,5,7,9,11},6
  2. 输出：7
  1. 输入：{5},5
  2. 输出：5

解答 & 代码

补充题 12. 二叉树的下一个结点 - 图2
节点 pNode 的中序遍历的下一个结点有 3 种可能：

  1. 若 pNode 有右子树，则其中序遍历的下一个节点为其右子树的最左节点。eg. 上图 2 的中序遍历的下一个结点为 8

  2. 若 pNode 没有右子树

    1. 若 pNode 是其父节点的左孩子，则 pNode 的父节点就是 pNode 中序遍历的下一个结点。eg. 上图 7 的中序遍历的下一个结点为 4

    2. 若 pNode 是其父节点的有孩子，则沿着父节点往上，直到找到一个节点的父节点的左孩子是该节点，则该节点的父节点就是 pNode 中序遍历的下一个结点。eg. 上图 9 的中序遍历的下一个结点为 1

      1. /*
      2. struct TreeLinkNode {
      3. int val;
      4. struct TreeLinkNode *left;
      5. struct TreeLinkNode *right;
      6. struct TreeLinkNode *next;
      7. TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
      9. }
      10. };
      11. */
      12. class Solution {
      13. public:
      14. TreeLinkNode* GetNext(TreeLinkNode* pNode) {
      15.   if(pNode == nullptr)
      16.       return nullptr;
      18.   // 1. 若 pNode 有右子树，则其中序遍历的下一个节点为其右子树的最左节点
      19.   if(pNode->right != nullptr)
      20.   {
      21.       TreeLinkNode* next = pNode->right;
      22.       while(next->left != nullptr)
      23.           next = next->left;
      24.       return next;
      25.   }
      26.   // 2. 若 pNode 没有右子树
      27.   // 2.1 若 pNode 是其父节点的左孩子，则 pNode 的父节点就是 pNode 中序遍历的下一个结点
      28.   else if(pNode->next != nullptr && pNode->next->left == pNode)
      29.       return pNode->next;
      30.   // 2.2 若 pNode 是其父节点的有孩子，则沿着父节点往上，直到找到一个节点的父节点的左孩子
      31.   // 是该节点，则该节点的父节点就是 pNode 中序遍历的下一个结点
      32.   else if(pNode->next != nullptr && pNode->next->right == pNode)
      33.   {
      34.       TreeLinkNode* next = pNode->next;
      35.       while(next->next != nullptr && next->next->left != next)
      36.           next = next->next;
      37.       return next->next;
      38.   }
      39.   else
      40.       return nullptr;
      41. }
      42. };

      复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(log N)：即二叉树的深度
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：5 ms
  4. 内存消耗：540 KB