LeetCode题目:Construct Binary Tree from Preorder and Inorder Traversal

By | 2012 年 12 月 11 日

这曾经是一道很难的题目,看来这一阵的锻炼确实是有效果的。


方法是,画一棵树出来,比如:

   1
 /   \
2     3
 \    /
  4  5

这棵树好用,在于其中包含了所有的可能性,(2度,1度(左右),0度节点都有)。
它的preorder是:1,2,4,3,5
他的inorder是:2,4,1,5,3


那么递归的看这个问题,首先preorder的第一个必然是根(1),然后此节点在inorder中的下标是2,那么在inorder中,处于1之前的两个节点2,4是左子树的;反之5,3是右子树的。
针对左子树,2,4就是它的inorder,而在preorder中,除开第一个根,数两个节点的子序列正好是2,4,这是左子树的preorder。这样这个问题就自然变成递归了:
即,其左子树的preorder是(2,4),inorder是(2,4);类似有右子树preorder(3,5),inorder(5,3)。
然后边界情况是某数的preorder和inorder遍历的长度都是1,比如{x},那么这棵树就是以x为值的节点。
这样就可以写出代码了。



Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.



代码:124ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef TreeNode TN;
class Solution {
    TN *buildTree(vector &preorder,int psi,int pei,
                  vector &inorder, int isi, int iei) {
        if(pei - psi < 0 || pei - psi != iei - isi) 
            return NULL;
        //root of sub tree
        TN *root = new TN(preorder[psi]);
        //find this value in inorder to locate the root in inorder
        int riii = -1;//root index in inorder
        for(int itemp = isi; itemp <= iei; ++ itemp) {
            if(inorder[itemp] == root->val) {
                riii = itemp;
                break;
            }
        }
        if(riii != -1) {
            //calculate the nodes count in left tree
            int leftCount = riii - isi;
            TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
            root->left = left;
            TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
            root->right = right;
        }
        return root;
    }
public:
    TreeNode *buildTree(vector &preorder, vector &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
    }
};

3 thoughts on “LeetCode题目:Construct Binary Tree from Preorder and Inorder Traversal

  1. Roger

    TreeNode *buildTree(vector &preorder, vector &inorder) {
    TreeNode* root = myBuild(preorder, 0, preorder.size() – 1, inorder, 0, inorder.size() – 1);
    }
    TreeNode* myBuild(vector &preorder, int pstart, int pend, vector &inorder, int istart, int iend)
    {
    if(iend < istart)
    return NULL;
    TreeNode* root = new TreeNode(preorder[pstart]);
    int i;
    for( i = istart; i left = myBuild(preorder, pstart + 1, pstart + left_len, inorder, istart, i – 1);
    root->right = myBuild(preorder, pstart + left_len + 1, pstart + left_len + right_len, inorder, i + 1, iend);
    return root;
    }

    Reply
    1. Roger

      网页显示有问题 查找当前节点在inorder array中位置的for循环没有正常显示。关键就是直接找,找到break,不需要设置临时变量

      Reply
      1. uniEagle Post author

        你把代码包含在<pre></pre>中就可以了,你试试。另外我没太明白你说的临时变量是指?

        Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注