《剑指offer》二叉树的下一个结点

【 声明:版权所有,转载请标明出处,请勿用于商业用途。 联系信箱:libin493073668@sina.com】

题目链接:?rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

我们通过画一个二叉树来观察特点,很明显要寻找满足题意特点的下一个结点满足以下条件。

1.如果一个结点有右子树,那么其下一个结点就是右子树中最左的结点

2.如果一个结点没有右子树,同时该结点是父结点的左子结点,那么其下一个结点就是父结点

3.如果一个结点既没有右子树,而且还是父结点的右子结点,,那么我们就要沿着父结点一层层往上遍历,直到找到一个新结点是其父结点的左子结点的时候,那么这个新结点的父结点就是我们要求的结点。

using namespace std;/*struct TreeLinkNode {int val;struct TreeLinkNode *left;struct TreeLinkNode *right;struct TreeLinkNode *next;TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}};*/class Solution{public:TreeLinkNode* GetNext(TreeLinkNode* pNode){if(pNode==nullptr)return nullptr;if(pNode->right!=nullptr){TreeLinkNode *pRight = pNode->right;while(pRight->left!=nullptr)pRight = pRight->left;return pRight;}else if(pNode->next!=nullptr){TreeLinkNode *pCurNode = pNode;TreeLinkNode *pParent = pNode->next;while(pParent!=nullptr && pCurNode == pParent->right){pCurNode = pParent;pParent = pParent->next;}return pParent;}}};

版权声明:本文为博主原创文章,如果转载,请注明出处

一起吃早餐,午餐,晚餐。或许吃得不好,

《剑指offer》二叉树的下一个结点

相关文章:

你感兴趣的文章:

标签云: