首页 > 代码库 > 算法题——二叉树结点的中序遍历的后继结点

算法题——二叉树结点的中序遍历的后继结点

2024-07-18 00:53:13   216人阅读

题目：给出二叉树的一个结点，返回它中序遍历顺序的下一个结点。

 

思路：

如果有指向父亲的结点，则：

  • 如果当前结点有右儿子，或者当前结点是根结点，则后继结点为右子树的最左叶节点；
  • 否则，如果当前结点是父结点的左儿子，则后继结点就是父结点；(其实是第三种情况的一个特例，即自己是第0代祖先，返回第一代祖先)
  • 否则，向上遍历，直到n-1代祖先是n代祖先的左儿子，则后继结点为n代祖先；或者遍历到根节点后未找到符合的n代结点，则该结点为中序遍历的最后结点，没有后继。

时间复杂度为树的高度O(lgN)。

代码： 

 1 //有父结点指针 2 struct TreeNode 3 { 4     int value; 5     TreeNode *parent; 6     TreeNode *left; 7     TreeNode *right; 8 }; 9 10 TreeNode *inorderSuccessor(TreeNode *node)11 {12     if(node == NULL)13         return NULL;14 15     TreeNode *successor = NULL;16 17     if(node->right != NULL || node->parent == NULL)  //有右子树，或者为根节点时，后继为右子树最左子结点18     {19         successor = node->right;20         while(successor != NULL && successor->left != NULL)  //根节点可能没有右子树，所以第一次要判断根的右儿子是否为空21         {22             successor = successor->left;23         }24     }25     else26     {27         while( (successor = node->parent) != NULL )28         {29             if(successor->left == node)     //当前结点是父结点的左儿子时，父结点就是后继30             {31                 break; 32             }33             node = successor;       //否则继续上溯34         }35     }36 37     return successor;38 }

 

如果没有指向父亲结点的指针，则必须给定根节点；中序遍历二叉树，用栈来进行非递归遍历；用cur_pop指向当前出栈的结点，prev指向上一出栈的结点；当prev_pop为输入结点时，cur_pop即为所求的后继结点。时间复杂度为O(N)。

代码：

 1 //没有父结点指针 2 struct TreeNode 3 { 4     int value; 5     TreeNode *left; 6     TreeNode *right; 7 }; 8  9 TreeNode *inorderSuccessor(TreeNode *root, TreeNode *node) //栈，中序遍历，记录出栈信息10 {11     if(root == NULL || node == NULL)12         return NULL;13 14     stack<TreeNode *> tns;15     tns.push(root);16 17     TreeNode *prev_pop, *cur_pop = NULL;    //prev_pop记录上一次出栈结点，cur_pop指向当前出栈结点18     TreeNode *ptn = root->left;             //ptn，遍历结点19 20     while( !tns.empty() || ptn != NULL )21     {22         if(ptn != NULL)         //当前结点不为空，入栈23         {24             tns.push(ptn);25             ptn = ptn->left;26         }27         else28         {29             prev_pop = cur_pop;30             cur_pop  = tns.top();31             tns.pop();          //栈头出栈32 33             if(prev_pop == node)34                 break;35 36             ptn = cur_pop->right;   //遍历出栈结点的右子树37         }38     }39 40     if(prev_pop == node)    //如果有后继41         return cur_pop;42     else43         return NULL;44 }

 


联系
我们