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

C++语言 码拜 6年前 (2015-10-20) 552次浏览
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
#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。你需要找到根。
解决方案:2分
是得到后继, 不需要中序遍历

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;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明二叉树找出中序遍历顺序的下一个结点并且返回
喜欢 (0)
[1034331897@qq.com]
分享 (0)