树的结构

//树的结构
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *parent;	//注意还有个父节点指针
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), parent(NULL) {   
    }
};

思路

一.如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说从右子节点出发一直沿着指向左子节点的指针，就能找到它的下一个节点。如b的下一个节点为h，a的下一个节点为f

二.1如果一个节点既没有右子树，并且它还是父节点的左子节点，那么它的下一个节点就是它的父节点

​ 2.如果一个节点既没有右子树，并且它还是父节点的右子节点，这种情况比较复杂，可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点，如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。例如，为了找到结点i的下一个结点，我们沿着指向父结点的指针，到达结点e。由于结点e是他父结点b的右结点，我们继续向上遍历到达结点b。结点b是它父节点a的左子结点。因此，结点a就是结点i的下一个结点。

代码

class Solution {
public:
	TreeLinkNode* GetNextNode(TreeLinkNode* pNode) {
		if (pNode == NULL)
			return NULL;
		TreeLinkNode* res = NULL;
		//一.有右子节点，寻找右子节点的最左子节点
		if (pNode->right != NULL) {
			TreeLinkNode* tmp = pNode->right;
			while (tmp->left != NULL)
				tmp = tmp->left;
		}
		else if (pNode->parent != NULL) {
			TreeLinkNode* curNode = pNode;
			TreeLinkNode* parentNode = pNode->parent;
			// 二.1 结点是其父结点的右子结点，沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点
			while (parentNode != NULL && curNode == parentNode->right) {
				curNode = parentNode;
				parentNode = parentNode->parent;
			}
			//二.2 结点是其父结点的左子结点，那么它的下一个结点就是其父结点
			res = parentNode;
		}
		return res;
	}
};