【每日一题】- 2019-08-05 - 105. 从前序与中序遍历序列构造二叉树

[azl397985856]

【每日一题】- 2019-08-05 - 105. 从前序与中序遍历序列构造二叉树

[raof01]

思路：

利用中序把数组划分成左右两个，定出左右子树在中序中的左右界（这里用到哈希表）。前序就好办，挨个遍历就好。有个tricky的地方，就是要保存前序目前处理到哪里了

代码：

class Solution {
private:
    int pos = 0;
private:
    TreeNode* genTree(vector<int>& pre, unordered_map<int, int>& m, int s, int e) {
        if (pos >= pre.size() || s > e) return nullptr;
        auto root = new TreeNode(pre[pos++]);
        if (s == e) return root;
        int loc = m.find(root->val)->second;
        root->left = genTree(pre, m, s, loc - 1);
        root->right = genTree(pre, m, loc + 1, e);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        auto m = unordered_map<int, int>();
        for (auto i = 0; i < inorder.size(); ++i) {
            m.insert(make_pair(inorder[i], i));
        }
        return genTree(preorder, m, 0, inorder.size() - 1);
    }
};

[azl397985856]

思路：

利用中序把数组划分成左右两个，定出左右子树在中序中的左右界（这里用到哈希表）。前序就好办，挨个遍历就好。有个tricky的地方，就是要保存前序目前处理到哪里了

代码：

class Solution {
private:
    int pos = 0;
private:
    TreeNode* genTree(vector<int>& pre, unordered_map<int, int>& m, int s, int e) {
        if (pos >= pre.size() || s > e) return nullptr;
        auto root = new TreeNode(pre[pos++]);
        if (s == e) return root;
        int loc = m.find(root->val)->second;
        root->left = genTree(pre, m, s, loc - 1);
        root->right = genTree(pre, m, loc + 1, e);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        auto m = unordered_map<int, int>();
        for (auto i = 0; i < inorder.size(); ++i) {
            m.insert(make_pair(inorder[i], i));
        }
        return genTree(preorder, m, 0, inorder.size() - 1);
    }
};

非常好。
题一个小优化点：hashmap实际上可以去掉

[xiongcaihu]

var buildTree = function (preorder, inorder) {
   if (preorder == null || preorder.length == 0) {
       return null;
   }
   if (preorder.length == 1) {
       return new TreeNode(preorder[0]);
   }
   var rn = new TreeNode(preorder[0]); // root node
   var rni = inorder.indexOf(preorder[0]); // root node index
   rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni));
   rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1));

   return rn;
};

[azl397985856]

var buildTree = function (preorder, inorder) {
   if (preorder == null || preorder.length == 0) {
       return null;
   }
   if (preorder.length == 1) {
       return new TreeNode(preorder[0]);
   }
   var rn = new TreeNode(preorder[0]); // root node
   var rni = inorder.indexOf(preorder[0]); // root node index
   rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni));
   rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1));

   return rn;
};

空间复杂度太高

[xiongcaihu]

var buildTree = function (preorder, inorder) {
   if (preorder == null || preorder.length == 0) {
       return null;
   }
   if (preorder.length == 1) {
       return new TreeNode(preorder[0]);
   }
   var rn = new TreeNode(preorder[0]); // root node
   var rni = inorder.indexOf(preorder[0]); // root node index
   rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni));
   rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1));

   return rn;
};

空间复杂度太高

其实要优化也简单，加几个位置变量就行了。

var buildTree = function (preorder, inorder) {
    return temp(0, preorder.length - 1, 0, inorder.length - 1);

    function temp(start, end, start2, end2) {
        if (start > end) {
            return null;
        } else if (start == end) {
            return new TreeNode(preorder[start]);
        }
        var rn = new TreeNode(preorder[start]); // root node
        var rni = inorder.indexOf(preorder[start], start2); // root node index
        rn.left = temp(start + 1, start + rni - start2, start2, rni - 1);
        rn.right = temp(start + 1 + rni - start2, end, rni + 1, end2);

        return rn;
    }
};

[azl397985856]

var buildTree = function (preorder, inorder) {
   if (preorder == null || preorder.length == 0) {
       return null;
   }
   if (preorder.length == 1) {
       return new TreeNode(preorder[0]);
   }
   var rn = new TreeNode(preorder[0]); // root node
   var rni = inorder.indexOf(preorder[0]); // root node index
   rn.left = buildTree(preorder.slice(1, 1 + rni), inorder.slice(0, rni));
   rn.right = buildTree(preorder.slice(1 + rni), inorder.slice(rni + 1));

   return rn;
};

空间复杂度太高

其实要优化也简单，加几个位置变量就行了。

var buildTree = function (preorder, inorder) {
    return temp(0, preorder.length - 1, 0, inorder.length - 1);

    function temp(start, end, start2, end2) {
        if (start > end) {
            return null;
        } else if (start == end) {
            return new TreeNode(preorder[start]);
        }
        var rn = new TreeNode(preorder[start]); // root node
        var rni = inorder.indexOf(preorder[start], start2); // root node index
        rn.left = temp(start + 1, start + rni - start2, start2, rni - 1);
        rn.right = temp(start + 1 + rni - start2, end, rni + 1, end2);

        return rn;
    }
};

你的操作好*啊， 还有闭包

[azl397985856]

参考答案：

/*
 * @lc app=leetcode id=105 lang=javascript
 *
 * [105] Construct Binary Tree from Preorder and Inorder Traversal
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function helper(preorder, pStart, pEnd, inorder, iStart, iEnd) {
  if (pStart > pEnd || iStart > iEnd) return null;
  const root = new TreeNode(preorder[pStart]);

  let i = iStart;
 
  while (inorder[i] !== root.val) {
    i++;
  }
  const len = i - iStart;
  root.left = helper(preorder, pStart + 1, pStart + len, inorder, iStart, i - 1);
  root.right = helper(preorder, pStart + len + 1, pEnd, inorder, i + 1, iEnd);
  return root;
}
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
  // tag: `tree`, `dfs`
  if (preorder.length !== inorder.length) return null;
  return helper(
    preorder,
    0,
    preorder.length - 1,
    inorder,
    0,
    inorder.length - 1
  );
};

[3460741663]

认领

[azl397985856]

认领

done

[codefool0307]

public class Tree_Reconstruct {
     public TreeNode preInToTreeNode(int[] pre,int[] in){
         if (pre==null ||in==null){
             return null;
         }
         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
         for (int i = 0; i < in.length; i++) {
             map.put(in[i],i);
         }
         return PreIn(pre,0,pre.length-1,in,0,in.length-1,map);
     }

     public  TreeNode PreIn(int[] p,int pi,int pj,int[] n,int ni,int nj,HashMap<Integer, Integer> map){
         if (pi>pj){
             return null;
         }
         TreeNode node = new TreeNode(p[pi]);
         //定义一个中序遍历头节点的索引值
         int index=map.get(p[pi]);
         node.left=PreIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
         node.right=PreIn(p,pi+index-ni+1,pj,n,index+1,nj,map);
         return node;
     }
}