【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
8二叉树中序遍历的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 分析： 结合图，我们可发现分成两大类： (1) 有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） (2) 没有右子树的，是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； (3) 没有右子树的，是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到遍历到的结点是其父节点的左孩子位置，返回该父结点。如果没有eg：M，那么他就是尾节点。 /* 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* p) {if(p == nullptr) return nullptr; if(p->right) //有右子树时，下个结点就是它右子树的最左子结点 {p = p->right; while(p->left != nullptr) p = p->left; return p; }else//没有右子树时，下个结点就是父结点（当前结点为左孩子时）或者向上遍历，以遍历到的结点为左孩子的父结点 {while(p->next) {if(p->next->left == p) //若为父结点的左结点，则父结点就是下一个结点 return p->next; else p = p->next; //往上查找，直到当前结点为父结点的左结点 } return nullptr; } } }; 简洁版： /** * 后继：求二叉树中序遍历的下一个结点 方法： (1) 有右子树的，那么下个结点就是右子树最左边的点；（在右边） (2) 没有右子树的，是父结点的左孩子，返回父结点；（在右边） (3) 没有右子树，是父结点的右孩子，从结点x开始向上查找，直到遍历到的结点是其父结点的左孩子位置，返回该父结点。（在右边） */ Node* BST_Successor(Node* node) {if(node->right) //有右子树时，下个结点为右子树最左结点 {Node *t = node->right; //右子树 while(t->left) t = t->left; return t; } else //无右子树时，返回父结点(向上查找，结点为左孩子的父结点) {Node* par = node->parent; //父结点 while(par && par->right == node) //如果当前结点是父结点的右孩子，向上遍历，直到当前结点为左结点 {node = par; par = par->parent; }//退出时，当前结点为父结点的左孩子 return par; //返回父结点 } }如果觉得《【LeetCode 剑指offer刷题】树题19：8 二叉树中序遍历的下一个结点》对你有帮助，请点赞、收藏，并留下你的观点哦！
