LeetCode 105. 已知前序&中序 求二叉树

1. 题目

类似POJ 2255 Tree Recovery

2. 解题

代码语言：javascript复制

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int,int> m;//哈希表
        for(int i = 0; i < inorder.size();   i) 
        {
        	m[inorder[i]] = i;//方便后面查找位置
        }
        return build(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1,m);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pS, int pE, int iS, int iE, unordered_map<int,int> &m)
    {
    	if(pS > pE)
    		return NULL;
    	TreeNode *root = new TreeNode(preorder[pS]);
    	int leftlen = m[preorder[pS]]-iS;
    	root->left = build(preorder,inorder,pS 1,pS leftlen,iS,m[preorder[pS]]-1,m);
    	root->right = build(preorder,inorder,pS 1 leftlen,pE,m[preorder[pS]] 1,iE,m);
    	return root;
    }
};

• 别人的循环解法，很牛，也很难理解

代码语言：javascript复制

class Solution {//别人写的，循环法
public:
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) 
    {
		if (pre.empty()) 
			return NULL;
		stack<TreeNode*> S;
		TreeNode* root = new TreeNode(pre[0]);
		S.push(root);
		for (int i = 1, j = 0; i < pre.size(); i  ) 
		{  // i-前序序号，j-中序序号
			TreeNode *back = NULL, *cur = new TreeNode(pre[i]);
			while (!S.empty() && S.top()->val == in[j]) 
			{
				back = S.top(), 
				S.pop(), 
				j  ;
			}	
			if (back)
			  	back->right = cur;
			else
			  	S.top()->left = cur;
			S.push(cur);
		}
		return root;
    }
};

tree

0 人点赞