191102题

思路：

#include<iostream> using namespace std; //左根右！！！ struct TreeNode { int value; TreeNode*left; TreeNode*right; TreeNode*parent; TreeNode(int x) :value(x), left(NULL), right(NULL), parent(NULL) {} }; class Solution { public: TreeNode*GetNext(TreeNode*pnode) { if (pnode == NULL) return NULL; TreeNode*pnext = NULL;//这种写法是个好习惯，考虑到了如果当前结点没有右子树也没有有父结点的情况 //如果当前结点有右子树，那么它的下一个结点就是它的右子树的最左子结点 if (pnode->right != NULL) { TreeNode*temp = pnode->right; while (temp->left != NULL) { temp = temp->left; } pnext = temp; } //如果当前结点没有右子树（但有父结点） else if (pnode->parent != NULL) { //第一种情况：它是父结点的左结点，那么很简单，它的下一个结点就是父结点 if (pnode == pnode->parent->left) pnext = pnode->parent; //第二种情况：它是父结点的右结点，那么我们要顺着父结点一直向上遍历，不断更新当前结点和当前结点的父结点，直到找到这样一个当前结点,该结点是它的父结点的左儿子。那么，该结点的父结点就是我们要找的结点。 else { TreeNode* current = pnode; while (current->parent != NULL&&current == current->parent->right)//核心 { current = current->parent; } pnext = current->parent; } } return pnext; } };