二叉树的下一个节点

方法一：暴力法

/*
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:
    vector<TreeLinkNode*> v;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* r = pNode;
        while(r->next)//找到根节点
            r = r->next;
        inorder(r);
        for(int i = 0;i < v.size();++i){
            if(v[i] == pNode && i+1 < v.size())
                return v[i+1];
        }
        return NULL;
    }
    void inorder(TreeLinkNode* r){
        if(!r)return;
        inorder(r->left);
        v.push_back(r);
        inorder(r->right);
    }
};

方法二：

分情况：

	 如果有右子树，那么中序的下一个为右子树的最后一个左子树
     如果没有右子树，判断节点在树的左子树还是右子树，如果左子树那么下一个就是它的父节点中的一个。如果在右为空。

/*
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) {
        if(pNode->right){//有右节点，即右节点的左子树即下一个节点
            pNode = pNode->right;
            while(pNode->left)
                pNode = pNode->left;
            return pNode;
        }
        while(pNode->next){//判断当前在树的左树还是右树
            if(pNode->next->left == pNode)//如果在左树
                return pNode->next;
            pNode = pNode->next;
        }
        return NULL;
    }
};