使用C++遍历树的心得，一个查询中序遍历下一个节点的实例

每次判断树的节点时候，要判断下一个节点是否为空。把这个作为判断条件，在一个就是不要使用过多的P->next->left这样的，应该给p->next设置一个中间变量保存好。

如下所示，我想要判断中序遍历下一个要遍历的节点。这个可以分为两步，这时候是否存在右子节点，之后该节点是否是父节点的左子节点。

在之后的判断中，我一开始使用了如下代码：

 1 //如果该节点是父节点的左子节点就返回父节点否则继续查找父节点是否是父节点的父节点的左子节点，依次往上
 2         TreeLinkNode* pNodeParentNode = pNode;
 3         if (pNodeParentNode->next != NULL)
 4         {
 5             while (pNodeParentNode != pNodeParentNode->next->left)
 6             {
 7                 if (pNodeParentNode->next != NULL)
 8                 {
 9                     pNodeParentNode = pNodeParentNode->next;
10                 } else {
11                     //如果一直找不到符合要求的父节点，说明已经遍历结束
12                     return NULL;
13                 }
14             }
15             return pNodeParentNode->next;
16         }

其实这时候第七行的判断父节点是否为空没有起到作用，因为已经在第五行被使用了。所以应该把判断是否为空放入条件里，如下所示：

 1 //如果该节点是父节点的左子节点就返回父节点否则继续查找父节点是否是父节点的父节点的左子节点，依次往上 
 2         TreeLinkNode* p = pNode;
 3         TreeLinkNode* pParentNode;
 4         while(p->next != NULL)
 5         {
 6             pParentNode = p->next;
 7             if (p == pParentNode->left)
 8             {
 9                 return pParentNode;
10             }
11             p = p->next
12         }

附中序遍历的下一个节点这个问题的最终答案：

 1 #include<iostream>
 2 using namespace std; 
 3 struct TreeLinkNode {
 4     int val;
 5     struct TreeLinkNode *left;
 6     struct TreeLinkNode *right;
 7     struct TreeLinkNode *next;
 8     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
 9         
10     }
11 };
12 class Solution {
13 public:
14     TreeLinkNode* GetNext(TreeLinkNode* pNode)
15     {
16         if (pNode == NULL)
17         {
18             return NULL;
19         }        
20         //如果这个节点的右子节点不为空，应该返回右子节点的最底层左子节点 
21         if (pNode->right != NULL)
22         {
23             TreeLinkNode* maxLeftChildNode = pNode->right;
24             while (true)
25             {
26                 if (maxLeftChildNode->left != NULL)
27                 {
28                     maxLeftChildNode = maxLeftChildNode->left;
29                 } else {
30                     return maxLeftChildNode;
31                 }     
32             }    
33         }
34         //如果该节点是父节点的左子节点就返回父节点否则继续查找父节点是否是父节点的父节点的左子节点，依次往上 
35         TreeLinkNode* p = pNode;
36         TreeLinkNode* pParentNode;
37         while(p->next != NULL)
38         {
39             pParentNode = p->next;
40             if (p == pParentNode->left)
41             {
42                 return pParentNode;
43             }
44             p = p->next
45         } 
46         //该节点是根节点而且该节点没有右子节点 
47         return NULL;
48     }
49 };
50 int main()
51 {
52     
53     return 0;
54 }