leetcode演算法之遞歸（一）

• 2021 年 1 月 31 日
• AI
• C/C++/C#

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

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

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

遞歸

• 104 二叉樹的最大深度 (Easy)
• 110 平衡二叉樹 (Easy)
• 543 二叉樹的直徑 (Easy)
• 226 翻轉二叉樹 (Easy)
• 617 合併二叉樹 (Easy)
• 112 路徑總和 (Easy)
• 572 另一個樹的子樹 (Easy)
• 101 對稱二叉樹 (Easy)
• 111 二叉樹的最小深度 (Easy)
• 404 左葉子之和 (Easy)
• 100 相同的樹 (easy)
• 257 二叉樹的所有路徑 (easy)

104 二叉樹的最大深度 (Easy)

• 題解：遞歸
  • 對於一棵樹，左子樹的最大深度l， 左子樹的最大深度為r。
  • 那麼整個樹的最大深度為l與r的較大值加上本身根節點的1.
  • 這裡求一棵樹的最大深度分別求了左右子樹的最大深度，形成遞歸結構。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if ( root == nullptr ) return 0;  
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return max(l, r) + 1;
    }
};

110 平衡二叉樹 (Easy)

• 遞歸
  • 一棵樹為平衡二叉樹，那麼根節點是平衡二叉樹， 左子節點與右右子節點均為平衡二叉樹， 形成遞歸結構
  • 利用上一題的最大深度

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs( maxDepth(root->left) - maxDepth(root->right) ) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int maxDepth( TreeNode* root){
        // 求一棵樹的深度（也就是最大深度）
        if (root == nullptr) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        return max(l, r) + 1;
    }
};

543 二叉樹的直徑 (Easy)

• 對於某個節點來說其做大的直徑為其左子樹的最大深度與右子樹最大深度之和加1.
• 依然是求最大深度問題
• 只是在每次計算過程中，需要替換最大的直徑。

class Solution {
public:
    int res = 1;  // 保存最大值
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return res - 1;
    }
    int maxDepth(TreeNode* root){
        if (root == nullptr) return 0;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);
        res = max(res, l + r + 1);
        return max(l , r) + 1;
    }
};

226 翻轉二叉樹 (Easy)

• 非常簡單，遍歷整個二叉樹，對於一個節點將其左右子樹交換即可。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 對於一個節點，交換其左右子樹的節點
        if (root == nullptr) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

617 合併二叉樹 (Easy)

• 其實就是一個遍歷的過程，直接採用前序遍歷。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

        if (t1 == nullptr && t2 == nullptr) return nullptr;
        if (t1 == nullptr) return t2;
        if (t2 == nullptr) return t1; 
        TreeNode* root = new TreeNode(t1->val + t2->val);
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

112 路徑總和 (Easy)

• 如果剛好遍歷到葉子節點，並且路徑和剛好為targetSum，返回True。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr ) return false;
        if(root->left == nullptr && root->right == nullptr && targetSum - root->val == 0) return true;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

572 另一個樹的子樹 (Easy)

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr) return true;
        if (s == nullptr || t== nullptr) return false;
		
		// 如果兩個節點均存在，如果值相等，判斷以這個開始的子樹是否相等， 相等返回true，不等的話繼續遍歷。
        if (s->val == t->val)
            if (equalTree(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool equalTree(TreeNode* t1, TreeNode* t2){
    // 判斷兩棵樹是否相等
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        return t1->val == t2->val && equalTree(t1->left, t2->left) && equalTree(t1->right, t2->right);
    }
};

101 對稱二叉樹 (Easy)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;

        return TreeSymmetric(root->left, root->right);
    }
    bool TreeSymmetric(TreeNode* s, TreeNode* t){
        // 判斷兩顆樹是否鏡面對稱。
        if (s== nullptr && t == nullptr) return true;
        if (s == nullptr || t == nullptr) return false;
        return s->val == t->val && TreeSymmetric(s->left, t->right) && TreeSymmetric(s->right, t->left);
    }
};

111 二叉樹的最小深度 (Easy)

• 這個題與最大深度的題目不一樣，不能直接左右子樹的最小值加1.因為其要求到葉子節點的距離
• 如果這棵樹是一條僅僅由左子樹構成的一條鏈表式的樹， 那麼直接左右子樹的最小值加1，結果返回就是1.
• 但是此時不滿足題意，題目要求到葉子節點。
• 正解需要分情況討論。見程式碼中分析。

class Solution {
public:
    int minDepth(TreeNode* root) {
        // 這個題與最大深度的題目不一樣，不能直接左右子樹的最小值加1.因為其要求到葉子節點的距離
        // 如果這棵樹是一條僅僅由左子樹構成的一條鏈表式的樹， 那麼直接左右子樹的最小值加1，結果返回就是1.
        // 但是此時不滿足題意，題目要求到葉子節點。

        if (root == nullptr) return 0;
        int l = minDepth(root->left);
        int r = minDepth(root->right);
        // 如果左子樹存在，右子樹不存在
        if (root->left != nullptr && root ->right == nullptr)
            return  l+ 1;
        // 如果左子樹不存在，右子樹存在
        if (root->right != nullptr && root->left == nullptr)
            return r + 1;
        // 左右子樹均存在。
        return min(l, r) + 1;
    }
};

404 左葉子之和 (Easy)

• 遍歷所有的節點， 將所有的左葉子節點求和即可。

class Solution {
public:
    int res = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr){
            res += root->left->val;
        }
        sumOfLeftLeaves(root->left);
        sumOfLeftLeaves(root->right);
        return res;
    }
};

100 相同的樹 (easy)

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        return (p->val == q->val ) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

257 二叉樹的所有路徑 (easy)

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;
        treePaths(root, res, path);
        return res;
    }
    
    void treePaths(TreeNode* root, vector<string>& res, string path){
    // 保存所有路徑
        if (root == nullptr) return;
        if(root->left == nullptr && root->right == nullptr) {
            path += to_string(root->val);
            res.push_back(path);
            return;
        }
        path += to_string(root->val);
        path += "->";
        treePaths(root->left, res, path);
        treePaths(root->right, res, path);
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn部落格： //blog.csdn.net/lxztju

• 知乎專欄： //www.zhihu.com/column/c_1101089619118026752

• AI研習社專欄：//www.yanxishe.com/column/109