513 找樹左下角的值

題目描述

給定一個(gè)二叉樹的 根節(jié)點(diǎn) root，請(qǐng)找出該二叉樹的 最底層 最左邊 節(jié)點(diǎn)的值。

假設(shè)二叉樹中至少有一個(gè)節(jié)點(diǎn)。

 

示例 1:



輸入: root = [2,1,3]
輸出: 1
示例 2:



輸入: [1,2,3,4,null,5,6,null,null,7]
輸出: 7
 

提示:

二叉樹的節(jié)點(diǎn)個(gè)數(shù)的范圍是 [1,104]
-231 <= Node.val <= 231 - 1 

我的想法

找出深度最大的葉子節(jié)點(diǎn)，左遍歷在前

題目分析

我們來分析一下題目：在樹的最后一行找到最左邊的值。

首先要是最后一行，然后是最左邊的值。

如果使用遞歸法，如何判斷是最后一行呢，其實(shí)就是深度最大的葉子節(jié)點(diǎn)一定是最后一行。

如果對(duì)二叉樹深度和高度還有點(diǎn)疑惑的話，請(qǐng)看：110.平衡二叉樹 (opens new window)。

所以要找深度最大的葉子節(jié)點(diǎn)。

那么如何找最左邊的呢？可以使用前序遍歷（當(dāng)然中序，后序都可以，因?yàn)楸绢}沒有 中間節(jié)點(diǎn)的處理邏輯，只要左優(yōu)先就行），保證優(yōu)先左邊搜索，然后記錄深度最大的葉子節(jié)點(diǎn)，此時(shí)就是樹的最后一行最左邊的值。

遞歸三部曲：

1. 確定遞歸函數(shù)的參數(shù)和返回值
   參數(shù)必須有要遍歷的樹的根節(jié)點(diǎn)，還有就是一個(gè)int型的變量用來記錄最長(zhǎng)深度。 這里就不需要返回值了，所以遞歸函數(shù)的返回類型為void。

本題還需要類里的兩個(gè)全局變量，maxLen用來記錄最大深度，result記錄最大深度最左節(jié)點(diǎn)的數(shù)值。

代碼如下：

int maxDepth = INT_MIN;   // 全局變量 記錄最大深度
int result;       // 全局變量 最大深度最左節(jié)點(diǎn)的數(shù)值
void traversal(TreeNode* root, int depth)

2. 確定終止條件
   當(dāng)遇到葉子節(jié)點(diǎn)的時(shí)候，就需要統(tǒng)計(jì)一下最大的深度了，所以需要遇到葉子節(jié)點(diǎn)來更新最大深度。

代碼如下：

if (root->left == NULL && root->right == NULL) {
    if (depth > maxDepth) {
        maxDepth = depth;           // 更新最大深度
        result = root->val;   // 最大深度最左面的數(shù)值
    }
    return;
}

3. 確定單層遞歸的邏輯
   在找最大深度的時(shí)候，遞歸的過程中依然要使用回溯，代碼如下：

                    // 中
if (root->left) {   // 左
    depth++; // 深度加一
    traversal(root->left, depth);
    depth--; // 回溯，深度減一
}
if (root->right) { // 右
    depth++; // 深度加一
    traversal(root->right, depth);
    depth--; // 回溯，深度減一
}
return;

acm模式完整代碼

#include <iostream>
#include <memory>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == nullptr && root->right == nullptr) {
            if(depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth ++;
            traversal(root->left, depth);
            depth --;
        }
        if (root->right) {
            depth ++;
            traversal(root->right, depth);
            depth --;
        }
        return;
    }


    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

int main() {
    // 使用智能指針創(chuàng)建樹節(jié)點(diǎn)
    std::unique_ptr<TreeNode> node1 = std::make_unique<TreeNode>(1);
    std::unique_ptr<TreeNode> node2 = std::make_unique<TreeNode>(2);
    std::unique_ptr<TreeNode> node3 = std::make_unique<TreeNode>(3);
    std::unique_ptr<TreeNode> node4 = std::make_unique<TreeNode>(4);
    std::unique_ptr<TreeNode> node5 = std::make_unique<TreeNode>(5);
    std::unique_ptr<TreeNode> node6 = std::make_unique<TreeNode>(6);
    std::unique_ptr<TreeNode> node7 = std::make_unique<TreeNode>(7);

    // 組織成樹（注意：這里我們使用裸指針，因?yàn)闃涞慕Y(jié)構(gòu)需要共享指針）
    node1->left = node2.get();
    node1->right = node3.get();
    node2->left = node4.get();
    node3->left = node5.get();
    node3->right = node6.get();
    node5->right = node7.get();

    // 使用 Solution 類的實(shí)例
    Solution solution;
    int result = solution.findBottomLeftValue(node1.get()); // 傳遞裸指針

    // 輸出結(jié)果
    std::cout << "The bottom left value is: " << result << std::endl;

    // 智能指針自動(dòng)釋放內(nèi)存
    return 0;
}

112 路徑總和

題目描述

給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum 。判斷該樹中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。如果存在，返回 true ；否則，返回 false 。

葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

 

示例 1：


輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目標(biāo)和的根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑如上圖所示。
示例 2：


輸入：root = [1,2,3], targetSum = 5
輸出：false
解釋：樹中存在兩條根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑：
(1 --> 2): 和為 3
(1 --> 3): 和為 4
不存在 sum = 5 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
示例 3：

輸入：root = [], targetSum = 0
輸出：false
解釋：由于樹是空的，所以不存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
 

提示：

樹中節(jié)點(diǎn)的數(shù)目在范圍 [0, 5000] 內(nèi)
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

我的思路

遍歷到葉子節(jié)點(diǎn)，記錄過程中值相加

題目分析

遞歸
可以使用深度優(yōu)先遍歷的方式（本題前中后序都可以，無所謂，因?yàn)橹泄?jié)點(diǎn)也沒有處理邏輯）來遍歷二叉樹

1. 確定遞歸函數(shù)的參數(shù)和返回類型
   參數(shù)：需要二叉樹的根節(jié)點(diǎn)，還需要一個(gè)計(jì)數(shù)器，這個(gè)計(jì)數(shù)器用來計(jì)算二叉樹的一條邊之和是否正好是目標(biāo)和，計(jì)數(shù)器為int型。

再來看返回值，遞歸函數(shù)什么時(shí)候需要返回值？什么時(shí)候不需要返回值？這里總結(jié)如下三點(diǎn)：

如果需要搜索整棵二叉樹且不用處理遞歸返回值，遞歸函數(shù)就不要返回值。（這種情況就是本文下半部分介紹的113.路徑總和ii）

如果需要搜索整棵二叉樹且需要處理遞歸返回值，遞歸函數(shù)就需要返回值。 （這種情況我們?cè)?36. 二叉樹的最近公共祖先 (opens new window)中介紹）

如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因?yàn)橛龅椒蠗l件的路徑了就要及時(shí)返回。（本題的情況）

而本題我們要找一條符合條件的路徑，所以遞歸函數(shù)需要返回值，及時(shí)返回，那么返回類型是什么呢？

遍歷的路線，并不要遍歷整棵樹，所以遞歸函數(shù)需要返回值，可以用bool類型表示

bool traversal(treenode* cur, int count)   // 注意函數(shù)的返回類型

2.確定終止條件
首先計(jì)數(shù)器如何統(tǒng)計(jì)這一條路徑的和呢？

不要去累加然后判斷是否等于目標(biāo)和，那么代碼比較麻煩，可以用遞減，讓計(jì)數(shù)器count初始為目標(biāo)和，然后每次減去遍歷路徑節(jié)點(diǎn)上的數(shù)值。

如果最后count == 0，同時(shí)到了葉子節(jié)點(diǎn)的話，說明找到了目標(biāo)和。

如果遍歷到了葉子節(jié)點(diǎn)，count不為0，就是沒找到。

遞歸終止條件代碼如下：

if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節(jié)點(diǎn)，并且計(jì)數(shù)為0
if (!cur->left && !cur->right) return false; // 遇到葉子節(jié)點(diǎn)而沒有找到合適的邊，直接返回

3. 確定單層遞歸的邏輯
   因?yàn)榻K止條件是判斷葉子節(jié)點(diǎn)，所以遞歸的過程中就不要讓空節(jié)點(diǎn)進(jìn)入遞歸了。

遞歸函數(shù)是有返回值的，如果遞歸函數(shù)返回true，說明找到了合適的路徑，應(yīng)該立刻返回。

if (cur->left) { // 左 （空節(jié)點(diǎn)不遍歷）
    // 遇到葉子節(jié)點(diǎn)返回true，則直接返回true
    if (traversal(cur->left, count - cur->left->val)) return true; // 注意這里有回溯的邏輯
}
if (cur->right) { // 右 （空節(jié)點(diǎn)不遍歷）
    // 遇到葉子節(jié)點(diǎn)返回true，則直接返回true
    if (traversal(cur->right, count - cur->right->val)) return true; // 注意這里有回溯的邏輯
}
return false;

以上代碼中是包含著回溯的，沒有回溯，如何后撤重新找另一條路徑呢。

回溯隱藏在traversal(cur->left, count - cur->left->val)這里， 因?yàn)榘裞ount - cur->left->val 直接作為參數(shù)傳進(jìn)去，函數(shù)結(jié)束，count的數(shù)值沒有改變。

為了把回溯的過程體現(xiàn)出來，可以改為如下代碼：

if (cur->left) { // 左
    count -= cur->left->val; // 遞歸，處理節(jié)點(diǎn);
    if (traversal(cur->left, count)) return true;
    count += cur->left->val; // 回溯，撤銷處理結(jié)果
}
if (cur->right) { // 右
    count -= cur->right->val;
    if (traversal(cur->right, count)) return true;
    count += cur->right->val;
}
return false;

完整代碼

#include <iostream>
# include <memory>
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true;
        if (!cur->left && !cur->right) return false;

        if (cur->left) {
            count -= cur->left->val;
            if(traversal(cur->left, count)) return true;
            count += cur->left->val;
        }
        if (cur->right) {
            count -= cur->right->val;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val;
        }
        return false;
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        return traversal(root, targetSum - root->val);
    }
};

int main() {
    // 創(chuàng)建樹節(jié)點(diǎn)
    std::unique_ptr<TreeNode> root = std::make_unique<TreeNode>(5);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    // 檢查路徑和
    Solution solution;
    bool hasPath = solution.hasPathSum(root.get(), 22);

    // 輸出結(jié)果
    if (hasPath) {
        std::cout << "There is a path with sum 22." << std::endl;
    } else {
        std::cout << "There is no path with sum 22." << std::endl;
    }

    // 清理分配的內(nèi)存
    delete root->left->left->left;
    delete root->left->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right->right->right;
    delete root->right->right;
    delete root->right->left;
    delete root->right;

    return 0;
}

106從中序與后續(xù)遍歷構(gòu)造二叉樹

題目描述

給定兩個(gè)整數(shù)數(shù)組 inorder 和 postorder ，其中 inorder 是二叉樹的中序遍歷， postorder 是同一棵樹的后序遍歷，請(qǐng)你構(gòu)造并返回這顆 二叉樹 。

 

示例 1:


輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]
示例 2:

輸入：inorder = [-1], postorder = [-1]
輸出：[-1]
 

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值組成
postorder 中每一個(gè)值都在 inorder 中
inorder 保證是樹的中序遍歷
postorder 保證是樹的后序遍歷

我的想法

先后序遍歷找到根節(jié)點(diǎn)，再用根節(jié)點(diǎn)再中序遍歷中進(jìn)行切割分為左序列和右序列

題目分析

說到一層一層切割，就應(yīng)該想到了遞歸。

來看一下一共分幾步：

第一步：如果數(shù)組大小為零的話，說明是空節(jié)點(diǎn)了。

第二步：如果不為空，那么取后序數(shù)組最后一個(gè)元素作為節(jié)點(diǎn)元素。

第三步：找到后序數(shù)組最后一個(gè)元素在中序數(shù)組的位置，作為切割點(diǎn)

第四步：切割中序數(shù)組，切成中序左數(shù)組和中序右數(shù)組 （順序別搞反了，一定是先切中序數(shù)組）

第五步：切割后序數(shù)組，切成后序左數(shù)組和后序右數(shù)組

第六步：遞歸處理左區(qū)間和右區(qū)間

TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {

    // 第一步
    if (postorder.size() == 0) return NULL;

    // 第二步：后序遍歷數(shù)組最后一個(gè)元素，就是當(dāng)前的中間節(jié)點(diǎn)
    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);

    // 葉子節(jié)點(diǎn)
    if (postorder.size() == 1) return root;

    // 第三步：找切割點(diǎn)
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }

    // 第四步：切割中序數(shù)組，得到 中序左數(shù)組和中序右數(shù)組
    // 第五步：切割后序數(shù)組，得到 后序左數(shù)組和后序右數(shù)組

    // 第六步
    root->left = traversal(中序左數(shù)組, 后序左數(shù)組);
    root->right = traversal(中序右數(shù)組, 后序右數(shù)組);

    return root;
}

難點(diǎn)大家應(yīng)該發(fā)現(xiàn)了，就是如何切割，以及邊界值找不好很容易亂套。

此時(shí)應(yīng)該注意確定切割的標(biāo)準(zhǔn)，是左閉右開，還有左開右閉，還是左閉右閉，這個(gè)就是不變量，要在遞歸中保持這個(gè)不變量。

在切割的過程中會(huì)產(chǎn)生四個(gè)區(qū)間，把握不好不變量的話，一會(huì)左閉右開，一會(huì)左閉右閉，必然亂套！

首先要切割中序數(shù)組，為什么先切割中序數(shù)組呢？

切割點(diǎn)在后序數(shù)組的最后一個(gè)元素，就是用這個(gè)元素來切割中序數(shù)組的，所以必要先切割中序數(shù)組。

中序數(shù)組相對(duì)比較好切，找到切割點(diǎn)（后序數(shù)組的最后一個(gè)元素）在中序數(shù)組的位置，然后切割，如下代碼中我堅(jiān)持左閉右開的原則：

// 找到中序遍歷的切割點(diǎn)
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
    if (inorder[delimiterIndex] == rootValue) break;
}

// 左閉右開區(qū)間：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

首先要切割中序數(shù)組，為什么先切割中序數(shù)組呢？

切割點(diǎn)在后序數(shù)組的最后一個(gè)元素，就是用這個(gè)元素來切割中序數(shù)組的，所以必要先切割中序數(shù)組。

中序數(shù)組相對(duì)比較好切，找到切割點(diǎn)（后序數(shù)組的最后一個(gè)元素）在中序數(shù)組的位置，然后切割，如下代碼中我堅(jiān)持左閉右開的原則：

// postorder 舍棄末尾元素，因?yàn)檫@個(gè)元素就是中間節(jié)點(diǎn)，已經(jīng)用過了
postorder.resize(postorder.size() - 1);

// 左閉右開，注意這里使用了左中序數(shù)組大小作為切割點(diǎn)：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

acm模式代碼

#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}

};

class Solution {
private:
    TreeNode* traversal(std::vector<int>& inorder, std::vector<int>& postorder) {
        if (postorder.size() == 0) return nullptr;
        
        int rootvalue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootvalue);

        if (postorder.size() == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootvalue) break;
        }

        std::vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        std::vector<int> rightInorder(inorder.begin() + delimiterIndex +1, inorder.end());

        postorder.resize(postorder.size() - 1);

        std::vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        std::vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
        
    }
public:
    TreeNode* buildTree(std::vector<int> &inorder, std::vector<int> &postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return nullptr;
        return traversal(inorder, postorder);
    }
};

void printTree(TreeNode* node) {
    if (node != nullptr) {
        printTree(node->left);
        printTree(node->right);
        std::cout << node->val << " ";

    }
}
int main() {
    // 創(chuàng)建中序和后序遍歷的序列
    std::vector<int> inorder = {9, 3, 15, 20, 7};
    std::vector<int> postorder = {9, 15, 7, 20, 3};

    // 創(chuàng)建Solution實(shí)例并重建二叉樹
    Solution solution;
    TreeNode* root = solution.buildTree(inorder, postorder);

    // 打印重建后的二叉樹結(jié)構(gòu)
    std::cout << "The reconstructed tree (inorder): ";
    printTree(root);
    std::cout << std::endl;

    // 注意：這里沒有刪除TreeNode的實(shí)例，實(shí)際應(yīng)用中應(yīng)考慮內(nèi)存管理

    return 0;
}

今日學(xué)習(xí)的文章和視頻鏈接

https://www.bilibili.com/video/BV1vW4y1i7dn/?vd_source=8272bd48fee17396a4a1746c256ab0ae
https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF文章來源地址http://www.zghlxwxcb.cn/news/detail-813068.html

到了這里，關(guān)于算法訓(xùn)練day18Leetcode找樹左下角的值112路徑總和106從中序和后續(xù)遍歷構(gòu)造二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！