从前序和中序遍历构造二叉树

/*
	 * 假设树的先序遍历是12453687，中序遍历是42516837。
	 * 这里最重要的一点就是先序遍历可以提供根的所在，
	 * 而根据中序遍历的性质知道根的所在就可以将序列分为左右子树。
	 * 比如上述例子，我们知道1是根，所以根据中序遍历的结果425是左子树，而6837就是右子树。
	 * 接下来根据切出来的左右子树的长度又可以在先序便利中确定左右子树对应的子序列
	 * （先序遍历也是先左子树后右子树）。
	 * 根据这个流程，左子树的先序遍历和中序遍历分别是245和425，
	 * 右子树的先序遍历和中序遍历则是3687和6837，我们重复以上方法，可以继续找到根和左右子树，
	 * 直到剩下一个元素。
	 */
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
	}

	private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
		if(preRight<preLeft)
			return null;
		TreeNode node=new TreeNode(preorder[preLeft]);
		if(preRight==preLeft)
            return node;
		int num=0;
		for(int i=inLeft;i<=inRight;i++){
			if(inorder[i]==preorder[preLeft]){
				num=i;
				break;
			}
		}
		int length=num-inLeft;
		
		node.left=buildTree(preorder,preLeft+1,preLeft+length,inorder,inLeft,inLeft+length-1);
		node.right=buildTree(preorder,preLeft+length+1,preRight,inorder,num+1,inRight);
		
		return node;
	}

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return build(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
    }
    TreeNode *build(vector<int> &preorder,vector<int> &inorder,int l1,int r1,int l2,int r2)
    {
    	if(l1 > r1)
    		return NULL;
    	int i,count=0,R = preorder[l1];
    	for(i=l2;i<=r2 && inorder[i]!=R;i++)
    		count++;
    	TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    	root->val = R;
    	root->left = build(preorder,inorder,l1+1,l1+count,l2,i-1);
    	root->right = build(preorder,inorder,l1+1+count,r1,i+1,r2);
		return root;
	}
};

/*经在leetcode上测试，借助hashmap可以提高不少效率，修改如下*/
import java.util.*;
public class Solution { 
    HashMap<Integer,Integer> in_map = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i <preorder.length; i++) 
            in_map.put(inorder[i],i);//借助hashmap存储元素在中序遍历中的下标
    	return helper(0, 0, inorder.length - 1, preorder, inorder);
}

    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = in_map.get(root.val); // 获取该根结点在中序遍历中的下标
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int prelen=preorder.length;
        int inlen=inorder.length;
        return BT(preorder,0,prelen-1,inorder,0,inlen-1);
    }
    TreeNode BT(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend)
    {
        if(instart>inend)
            return null;
        TreeNode root=new TreeNode(preorder[prestart]);
        int mid=0;
        for(mid=instart;mid<=inend;mid++)
            if(inorder[mid]==root.val)
                break;
        int leftlen=mid-instart;
        root.left=BT(preorder,prestart+1,prestart+leftlen,inorder,instart,mid-1);
        root.right=BT(preorder,prestart+leftlen+1,preend,inorder,mid+1,inend);
        return root;
    }
}

    /*
    * 目的：前+中->二叉树
    * 思路：1.首先根据前序遍历获得根节点
    *      2.在中序遍历中寻找根节点，进而得到左右子树的中序遍历
    *      3.根据左右子树中序遍历的数量，确定左右子树的前序遍历
    *      4.递归左右子树求解
    */
    TreeNode*getres(vector<int>&preorder,int prestart, int preend, vector<int>&inorder, int instart, int inend){
        if (prestart>preend|| instart>inend)
            return nullptr;
        int pos = instart;
        for (;pos<=inend;++pos){
            if (preorder[prestart]== inorder[pos]){
                break;
            }
        }
        TreeNode*root = new TreeNode(preorder[prestart]);
        int len = pos-instart;
        root->left = getres(preorder, prestart+1,prestart+len,inorder, instart, pos-1);
        root->right = getres(preorder, prestart+len+1, preend,inorder, pos+1,inend);
        return root;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int len = preorder.size();
        return getres(preorder,0, len-1 ,inorder,0, len-1);
    }

//C++迭代器
class Solution {
    void buildTree(TreeNode*& root, vector<int>::iterator pre_begin, vector<int>::iterator pre_end, vector<int>::iterator in_begin, vector<int>::iterator in_end)
    {
        if (pre_begin == pre_end) {
            root = nullptr;
            return;
        }
        root = new TreeNode(*pre_begin);
        auto it = find(in_begin, in_end, *pre_begin);
        buildTree(root->left, pre_begin + 1, pre_begin + 1 + (it - in_begin), in_begin, it);
        buildTree(root->right, pre_begin + (it - in_begin) + 1, pre_end, it + 1, in_end);
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        TreeNode* root;
        buildTree(root, preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
        return root;
    }
};

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    
    public TreeNode helper(int[] preorder, int[] inorder, int preBegin, int preEnd, int inBegin, int inEnd){
        if(preBegin > preEnd) return null;
        int value = preorder[preBegin];
        TreeNode root = new TreeNode(value);
        int preMid = preBegin + 1, inMid = inBegin;
        for(int i = inBegin; i <= inEnd; i++){
            if(inorder[i] == value) break;
            preMid++; inMid++;
        }
        root.left = helper(preorder, inorder, preBegin + 1, preMid - 1, inBegin, inMid - 1);
        root.right = helper(preorder, inorder, preMid, preEnd, inMid + 1, inEnd);
        return root;
    }
}

/*
递归求解。
先序遍历的第一个节点为当前根节点。
中序遍历该数的左边序列为当前节点左子树的中序遍历序列。
右边序列为右子数的中序遍历序列。
*/
public class Solution {
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return decideNode(0, 0, inorder.length - 1);
    }

    public TreeNode decideNode(int loc, int beg, int end) {
        if (beg > end)
            return null;
        int mid = 0;
        int cnt = 0; //左子树的长度。
        for (int i = beg; i <= end; i++) {
            cnt++;
            if (preorder[loc] == inorder[i]) {
                mid = i;
                break;
            }
        }
        TreeNode node = new TreeNode(preorder[loc]);
        node.left = decideNode(loc + 1, beg, mid - 1);
        node.right = decideNode(loc + cnt, mid + 1, end);
        return node;
    }
}

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // Construct Binary Tree from Preorder and Inorder Traversal
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) {
        return constructBiTree(pre, 0, pre.size() - 1, in, 0, in.size() - 1);
    }

    TreeNode* constructBiTree(vector<int> pre, int preStart, int preEnd, vector<int> in, int inStart, int inEnd) {
        // 递归终结条件
        if(preStart > preEnd || inStart > inEnd) return nullptr;

        int value = pre[preStart];
        int index;
            // 在中序序列中查找根节点
        if((index = searchNode(in, value)) == in.size()) return nullptr;

        // 构造根节点
        TreeNode *root = new TreeNode(value);
        int len = index - inStart;  // 记录左子树长度
        // 递归地构造左右子树
        root->left = constructBiTree(pre, preStart + 1, preStart + len, in, inStart, index - 1);
        root->right = constructBiTree(pre, preStart + len + 1, preEnd, in, index + 1, inEnd);
        return root;
    }

    // 在中序序列中查找根节点
    int searchNode(vector<int> in, int e) {
        int i;
        for(i = 0; i < in.size(); i++)
            if(in[i] == e)
                break;
        return i;
    }

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return f(preorder,0,preorder.length,inorder,0,preorder.length);
    }
     public TreeNode f(int[] pre,int s,int e,int []mid,int s1,int e1){
        if(s==e) return null;
        TreeNode t = new TreeNode(pre[s]);
        int i=s1;
        for(;i<e1;i++)
            if(mid[i]==pre[s]) break;
        t.left=f(pre,s+1,s+i-s1+1,mid,s1,i);
        t.right=f(pre,s+i-s1+1,e,mid,i+1,e1);
        return t;
    }
}

TreeNode *dfs(vector<int> &preorder,int preStart,int preEnd,vector<int> &inorder,int inStart,int inEnd)
{
    if(preStart > preEnd)
        return nullptr;
    TreeNode *root = new TreeNode(preorder[preStart]);
    int middle;
    for(middle=inStart;middle<=inEnd;middle++)
        if(inorder[middle] == root->val)
            break;
    int leftLen = middle-inStart;
    root->left = dfs(preorder,preStart+1,preStart+leftLen,inorder,inStart,middle-1);
    root->right = dfs(preorder,preStart+leftLen+1,preEnd,inorder,middle+1,inEnd);
    return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
    int pre = preorder.size(),in = inorder.size();
    if(pre==0 || in==0 || pre != in)
        return nullptr;
    return dfs(preorder,0,pre-1,inorder,0,in-1);
}

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return build(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
    }
    TreeNode *build(vector<int> &preorder, vector<int> &inorder,int l1,int r1,int l2,int r2)
    {
        if(l1>r1)
            return NULL;
        int gen=preorder[l1],i,cnt=0;
        for(i=l2;i<=r2&&inorder[i]!=gen;cnt++,i++);
        TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode));
        root->val=gen;
        root->left=build(preorder,inorder,l1+1,l1+cnt,l2,i-1);
        root->right=build(preorder,inorder,l1+1+cnt,r1,i+1,r2);
        return root;
    }
};

class Solution {
public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    function<TreeNode*(int, int, int)> build = [&](int i, int j, int n) -> TreeNode* {
      if (n <= 0) return (TreeNode*) nullptr;
      auto root = new TreeNode(preorder[i]);
      if (n == 1) return root;
      
      int k = j;
      while (inorder[k] != preorder[i]) ++k;
      int l = k - j;
      
      root->left = build(i + 1, j, l);
      root->right = build(i + 1 + l, k + 1, n - 1 - l);
      return root;
    };
    
    return build(0, 0, preorder.size());
  }
};

class Solution:
    def buildTree(self , preorder , inorder ):
        # write code here
        node = None
        if preorder:
            node = TreeNode(preorder[0])
            index = inorder.index(preorder[0])
            node.left = self.buildTree(preorder[1:1 + index], inorder[:index])
            node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return node

采用先序遍历的思想构建即可。

编码过程中，遇到了一个bug，只能通过25%的样例，反复检查逻辑问题，没有什么差错，最后面发现，原来是把第36行的==写成了=2333。总结：定位bug需要从多方面考虑：

1. 如果是样例通过不了：考虑算法思路是否有误、运算符是不是写错了
2. 如果是编译错误：考虑语法问题
3. 如果是段错误、溢出：考虑边界问题，尤其是指针和数组下标

//
// Created by jt on 2020/8/21.
//
#include <vector>
using namespace std;


struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val): val(val), left(0), right(0) {}
};


class Solution {
public:
    /**
     *
     * @param preorder int整型vector
     * @param inorder int整型vector
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // write code here
        int size = preorder.size();
        return inOrder(preorder, 0, size - 1, inorder, 0, size -1);
    }

    TreeNode* inOrder(vector<int> &preorder, int pL, int pR,
                      vector<int> &inorder, int iL, int iR) {
        if (pL > pR) return nullptr;
        TreeNode *root = new TreeNode(preorder[pL]);
        int mid = iL;
        for (; mid <= iR; ++mid)
            if (inorder[mid] == root->val) break;
        int sizeLeft = mid - iL;
        // 中左右 左中右
        root->left = inOrder(preorder, pL+1, pL+sizeLeft, inorder, iL, mid-1);
        root->right = inOrder(preorder, pL+sizeLeft+1, pR, inorder, mid+1, iR);
        return root;
    }
};

/**
总结
前序和中序的规律是
同为长为n的序列
长为k的左子树 根 长为n-k-1的右子树
根 长为k的左子树 长为n-k-1的右子树

1、确定两个序列中根所在的位置后
2、截出两个左子树序列，继续找左子树的根，将其作为上一根节点的左节点
2、截出两个右子树序列，继续找右子树的根，将其作为上一根节点的右节点
3、递归找根，直到子树为空时结束

**/

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||inorder==null){
            return null;
        }
        return travel(preorder,inorder,0 ,preorder.length-1 , 0,inorder.length-1);
    }
    public TreeNode travel(int[] preorder, int[] inorder ,int prex , int prey, int inx,int iny ){
        if(prex>prey || inx>iny){
            return null;
        }
        TreeNode node = new TreeNode(preorder[prex]);
        
        for (int k = 0 ; inx+k<=iny ; k++){ 
        //注：最好用0，若用inx作为起始，需要减去inx得到相对长度来截取后序遍历。
            if(inorder[inx+k]==preorder[prex]){
                node.left = travel(preorder,inorder,prex+1 , prex+ k+1 , inx,inx+ k-1);
                node.right = travel(preorder,inorder,prex+ k+1 , prey , inx+ k+1,iny);
                
            }
        }
        return node;
    }
}