小白一次AC LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal的要点


题目意思是,给你一颗树的前序遍历和中序遍历,让你重建这棵树。

这道题本科数据结构是讲过的,期末考试,考研这种题目也经常有,LeetCode刷题班又听许老师讲了一遍,老师思路讲的很好了,我就说说本题目如何练自己一次Bug-Free的能力,一次AC的要点在于
  1. 中序遍历找到根节点后,算出到中序遍历左子树的数量n,那么前序遍历根节点后n个就是左子树的节点,根节点以后的就是右子树的节点,不明白的画几个例子。
  2. 快速写出处理树常见问题的框架代码。
  3. 根据要点1,计算出左右子树的开始和结束下标,注意整数前开后闭区间[st, end)一共有end - st个数,[st, end]有end-st 1个数,不懂的童鞋算一下就好。
  4. 然后只要把左右子树的下标填补进去,我下面给出了两种写法本质是一样的,都是一次AC。


Construct Binary Tree from Preorder and Inorder Traversal Accepted 20 ms cpp
Construct Binary Tree from Preorder and Inorder Traversal Accepted 30 ms cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode *ansRoot = NULL;
        
        if (preorder.size() && inorder.size() == 0){
            return ansRoot;
        }
        
        ansRoot = ConstructTree(ansRoot, preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        
        return ansRoot;
    }
    
    TreeNode *ConstructTree(TreeNode * root, vector<int> &pre, int st1, int end1, vector<int> &in, int st2, int end2){
        if (st1 >= pre.size() || st2 > end2){
            return NULL;
        }
        
        root = new TreeNode(pre[st1]);
        
        int pos = -1;
        for (int i = st2; i <= end2; ++i){
            if(in[i] == pre[st1]){
                pos = i;
            }
        }
        
        if (pos == -1){
            return NULL;
        }
        
        int nLeft = pos - st2;//因为pos是跟节点,所以[)区间可以直接减
        root->left  = ConstructTree(root, pre, st1 + 1,            st1 + nLeft - 1, in, st2,     pos - 1);
        root->right = ConstructTree(root, pre, st1 + nLeft + 1,    end1,            in, pos + 1, end2   );
        
        //root->left  = ConstructTree(root, pre, st1 + 1,            st1 + nLeft - 1, in, st2,     st2 + nLeft - 1);
        //root->right = ConstructTree(root, pre, st1 + nLeft + 1,    end1,            in, st2 + nLeft + 1, end2   );
        
        return root;
    }
    
};

0 个评论

要回复文章请先登录注册

返回顶部