By

题目描述

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

题目解析

本题可以分为几点进行考虑
1.当给定的节点pNode存在右子节点时，其中序遍历的下一个节点就是其右子节点的最左子节点，若pNode的右子节点无左子树，即为pNode的右子节点本身。
2.若给定的节点pNode不存在右子节点，且pNode的父节点不为空，pNode为其父节点的左子节点，则中序遍历的下一个节点为pNode的父节点。
3.若给定的节点pNode不存在右子节点，且pNode的父节点不为空，pNode为其父节点的右子节点，pNode父节点为pNode父节点的父节点的左子节点，则中序遍历的下一个节点为pNode父节点的父节点。
4.不满足以上三种情况，则返回空。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
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)
    {  
        //next
        TreeLinkNode* p=pNode;
        if(p->right!=NULL){
            p=p->right;
            while(p->left!=NULL){
                p=p->left;
            }
            return p;
        }
         
        p=pNode;
        if(p->next!=NULL){
            //left
            if(p->next->left==p) return p->next;
         
            //right
            p=p->next;
            if(p->next->left==p)
                return p->next;
        }
        return NULL;
    }
};