leetcode演算法之遞歸（二）

今天來盤一盤 **遞歸 ** 這類題目

這類題目是我一直很頭疼的題目, 感覺有點難, 從這篇文章開始,就要開始比較難的一部分了

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

遞歸

  • 222 完全二叉樹的節點個數 (medium)
  • 687 最長同值路徑 (medium)
  • 113 路徑總和 II (medium)
  • 129 求根到葉子節點數字之和 (medium)
  • 437 路徑總和 III (medium)

222 完全二叉樹的節點個數 (medium)

  • 方法1： 不考慮完全二叉樹，直接遍歷所有的節點
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int l = countNodes(root->left);
        int r = countNodes(root->right);
        return (l + r + 1);
    }
};
  • 方法2： 利用完全二叉樹的性質

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        // 分別求左右兩顆子樹的高度
        int l = treeDepth(root->left);
        int r = treeDepth(root->right);
        // 如果兩顆子樹高度相等，說明左子樹為滿二叉樹，右子樹不滿
        if (l == r){
            return pow(2, l) + countNodes(root->right);
        }
        // 高度不等，說明右子樹是滿二叉樹，左子樹不滿。
        else
            return pow(2, r) + countNodes(root->left);
    }
    int treeDepth(TreeNode* root){
    //求一棵完全二叉樹的高度
        if (root == nullptr) return 0;
        int l = treeDepth(root->left);
        return l + 1;
    }
};

687 最長同值路徑 (medium)

  • 最長同值路徑就是過某個節點最長同值路徑中的最大值。
class Solution {
public:
    int res = 0;
    int longestUnivaluePath(TreeNode* root) {
        if (root == nullptr) return 0;
        arrowLength(root);
        return res;
    }
    int arrowLength(TreeNode* root){
    // 以某個節點作為根節點的最長同值路徑。
        if (root == nullptr) return 0;
        int l = arrowLength(root->left);
        int r = arrowLength(root->right);
        int left = 0, right = 0;
        if (root->left != nullptr && root->val == root->left->val)
            left = l + 1;
        if (root->right != nullptr && root->val == root->right->val)
            right = r + 1; 
        res = max(res, left + right);
        return max(left, right);
    }
};

113 路徑總和 II (medium)

  • 套路程式碼
class Solution {
public:
    
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int> > res;
        vector<int> path;
        pathsum(root, res, path, targetSum);
        return res;
    }
    void pathsum(TreeNode* root, vector<vector<int>>& res, vector<int> path, int target){
        if (root == nullptr) return;
        if (root->left == nullptr && root->right == nullptr && target == root->val){
            path.push_back(root->val);
            res.push_back(path);
            return ;
        }
        path.push_back(root->val);
        target -= root->val;
        pathsum(root->left, res, path, target);
        pathsum(root->right, res, path, target);
        return ;            
    }
};

129 求根到葉子節點數字之和 (medium)

  • 先求出所有的路徑， 然後求和。
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        vector<vector<int> > res;
        vector<int> path;
        Path(root, res, path);
        int ans = 0;
        for (int i=0; i < res.size(); i++){
            int tmp = 0;
            for (int j = res[i].size()-1; j >= 0; j--){
                tmp += (res[i][j] * pow(10, res[i].size()-1 - j));
            }
            ans += tmp;
        }
        return ans;
    }

    void Path(TreeNode* root, vector<vector<int>>& res, vector<int> path){
    // 得到所有的路徑，保存至vector中
        if (root == nullptr) return;
        if (root->left == nullptr && root->right == nullptr ){
            path.push_back(root->val);
            res.push_back(path);
            return ;
        }
        path.push_back(root->val);
        Path(root->left, res, path);
        Path(root->right, res, path);
        return ;            
    }
};

437 路徑總和 III (medium)

class Solution {
public:
    int res = 0;
    int pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return 0;
        // 以根節點開始
        pathsum(root, sum);
        //  遍歷整個樹
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        return res;
    }
    void pathsum(TreeNode* root, int target){
        // 以某個節點開始一共有多少路徑和為target的路徑。
        if (root == nullptr) return ;
        target -= root->val;
        if (target == 0){
            res += 1;
        }
        pathsum(root->left, target);
        pathsum(root->right, target);
        return ;
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS

QNews

QNews