二叉树找出中序遍历顺序的下一个结点并且返回

码拜

10年 ago

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

#include <iostream>
#include <vector>
using namespace std;
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 *> ve;
	void in_order(TreeLinkNode* t)
	{
		if(t)
		{
			in_order(t->left);
			ve.push_back(t);
			in_order(t->right);
		}
	}
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {

        TreeLinkNode *header,*p; 
		p = pNode;
		if(p!=NULL)
		{
          header = p;
		  p = p->next;
		}
        in_order(header);
		int i,len;
		len  = ve.size();
		for(i=0;i<len;i++)
		{
           if(ve[i]== pNode)
		   {
			   if(i == len-1) return NULL;
			   else return ve[i+1];
		   }
		   
		}

    }
    
};

中序遍历树，然后把结点存在向量之后再去比对，为啥没通过所有测试用例

解决方案：28分

33…37 行，不是 if ，而是 while。你需要找到根。

是得到后继, 不需要中序遍历的

TreeLinkNode *tree_min(TreeLinkNode *p) { while(p->left) p =p->left; return p }
TreeLinkNode *tree_next(TreeLinkNode *p) { 
     if(p->right) return tree_min(p->right); 
    auto res =x->parent; 
   while(res && p ==res->right) p =res, res=p->parent;
   return res;
}