【剑指offer】二叉树的下一个结点（树）

本文主要是介绍【剑指offer】二叉树的下一个结点（树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

链接

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

代码

class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* pNode){if(pNode == NULL){return NULL;}TreeLinkNode* ans = NULL;if(pNode->right){ // 有右子树的情况为右子树上最左边的点ans = pNode->right;while(ans->left){ans = ans->left;}}else{if(pNode->next && pNode == pNode->next->left){ // 父节点的左子树，答案就是父节点ans = pNode->next;}if(pNode->next && pNode == pNode->next->right){ // 父节点的右子树，一直往上找，直到为左子树ans = pNode;TreeLinkNode* father = pNode->next;while(ans == father->right){ans = father;if(father->next){father = father->next;}else{father = NULL;break;}}ans = father;}}return ans;}
};

这篇关于【剑指offer】二叉树的下一个结点（树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---