c++和python前序遍历构造bst的解决方案区别

Question

虽然这个解决方案在 O(n^2) 中完成。真正让我着迷的是 C++ 中的相同解决方案被接受，而 python 版本抛出 error.I 我是新手C ++。任何帮助都将是 appreciated.The 在 buildBST 函数中传递的根始终假定它在 python 中为 Null。

C++代码

TreeNode *buildBST(TreeNode* &root, int ele) {
    if(!root)
        return root = new TreeNode(ele);
    
    if(root->val > ele)
        root->left = buildBST(root->left, ele);
    else
        root->right = buildBST(root->right, ele);
    
    return root;
}
TreeNode* bstFromPreorder(vector<int>& pre) {
    TreeNode *root = NULL;
    
    for(auto x : pre)
        buildBST(root, x);
    
    return root;
}

这里是 python 版本：

def buildBST(self,root,ele): 
    if root is None:
        root = TreeNode(ele)
        return root

    if(root.data > ele):
        root.left = self.buildBST(root.left, ele)
    else:
        root.right = self.buildBST(root.right, ele)

    return root
def bstFromPreorder(self,pre):
    root = None
    
    for i in pre:
        
        self.buildBST(root, i)
        
    
    return root

Answer 1

root 是 C++ 中的指针引用

TreeNode *buildBST(TreeNode* &root, int ele) {

root只是Python

中的一个参数

def buildBST(self,root,ele):

当您的代码在 return 之前更改 root 的值时，它对您的 Python 代码没有影响。

大概应该是：

def buildBST(self, root, ele):
    if root is None:
        root = TreeNode(ele)
        return root

    if(root.data > ele):
        root.left = self.buildBST(root.left, ele)
    else:
        root.right = self.buildBST(root.right, ele)

    return root

def bstFromPreorder(self, pre):
    root = None
    for i in pre:
        root = self.buildBST(root, i)  # changed here
    return root

c++和python前序遍历构造bst的解决方案区别

Difference between c++ and python solution of constructing bst from preorder traversal

c++

python

binary-tree