#129求根到葉數(shù)字之和

回溯放進vector，然后從后往前拿，乘1 10 100 ... 很基礎的回溯

my code：

    void backtrack(int depth, TreeNode* cur, vector<TreeNode*> &vec, int &sum){
        if(cur->left==nullptr &&cur->right==nullptr){
            size_t a=1;
            for(int i=vec.size()-1;i>=0;i--){
                sum+=vec[i]->val*a;
                a*=10;
            }
        
            return;
        }
        if(cur->left){
            vec.push_back(cur->left);
            backtrack(depth+1,cur->left, vec, sum);
            vec.pop_back();
        }
        if(cur->right){
            vec.push_back(cur->right);
            backtrack(depth+1,cur->right,vec, sum);
            vec.pop_back();
        }
    }

    int sumNumbers(TreeNode* root) {
        int sum=0;
        vector<TreeNode*> vec={root};
        
        backtrack(1,root,vec,sum);
        return sum;
    }

隨想錄跟我思路差不多，但這兩個是放globa的：int result; vector<int> path; 最近總覺得global不安全不想放?

#1382二叉樹變平衡

本來遇到這種會換root的就頭疼，然后看了眼隨想錄，是要先變成vec，再從vec重構，就會了

mycode：

    vector<int> vec;

    void inorder(TreeNode* node){
        if(node==nullptr) return;
        inorder(node->left);
        vec.push_back(node->val);
        inorder(node->right);
    }

    TreeNode* build_tree(int start, int end){
        if(start>end) return nullptr;
        TreeNode* root= new TreeNode();
        int mid=(start+end)/2;
        int val=vec[mid];
        root->val=val;
        root->left=build_tree(start, mid-1);
        root->right=build_tree(mid+1, end);
        return root;
    }

    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return build_tree(0,vec.size()-1);
     
    }

#100相同的樹 easy

以任何方式遍歷比較即可：和隨想錄一模一樣文章來源地址http://www.zghlxwxcb.cn/news/detail-620210.html

    bool traverse(TreeNode* n1, TreeNode* n2){
        if(n1==nullptr && n2==nullptr) return true;
        if(n1==nullptr && n2) return false;
        if(n1 && n2==nullptr) return false;
        if(n1->val!=n2->val) return false;
        
        return traverse(n1->left, n2->left) && traverse(n1->right, n2->right);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        return traverse(p,q);
        
    }

到了這里，關于代碼隨想錄額外題目| 二叉樹 ●129求根到葉數(shù)字之和 ●1382二叉樹變平衡●100相同的樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！