My neat C++ solution


  • 25
    H
    class Solution {
    
    public:
        /* from Preorder and Inorder Traversal */
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    
            return helper(preorder,0,preorder.size(),inorder,0,inorder.size());
        
        }
    
        TreeNode* helper(vector<int>& preorder,int i,int j,vector<int>& inorder,int ii,int jj)
        {
            // tree        8 4 5 3 7 3
            // preorder    8 [4 3 3 7] [5]
            // inorder     [3 3 4 7] 8 [5]
    
            // 每次从 preorder 头部取一个值 mid,作为树的根节点
            // 检查 mid 在 inorder 中 的位置,则 mid 前面部分将作为 树的左子树,右部分作为树的右子树
    
            if(i >= j || ii >= j)
                return NULL;
    
            int mid = preorder[i];
            auto f = find(inorder.begin() + ii,inorder.begin() + jj,mid);
    
            int dis = f - inorder.begin() - ii;
    
            TreeNode* root = new TreeNode(mid);
            root -> left = helper(preorder,i + 1,i + 1 + dis,inorder,ii,ii + dis);
            root -> right = helper(preorder,i + 1 + dis,j,inorder,ii + dis + 1,jj);
            return root;
        }
    };

  • 0

    really neat and readable


  • 0
    S

    上面的中文注释,暴露了题主的国家,哈哈哈。。。


  • 1
    J

    brilliant comments!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.