算法訓練 | 二叉樹Part5 | 513.找樹左下角的值、112.路徑總和、106.從中序與后序遍歷序列構造二叉樹

513.找樹左下角的值

遞歸法

迭代法 ?

112.路徑總和

遞歸法

迭代法

106.從中序與后序遍歷序列構造二叉樹

遞歸法

513.找樹左下角的值

題目鏈接：513. 找樹左下角的值 - 力扣（LeetCode）
文章講解：programmercarl.com

遞歸法

解題思路
- 在樹的最后一行找到最左邊的值。首先要是最后一行，然后是最左邊的值。如果使用遞歸法，如何判斷是最后一行呢，其實就是深度最大的葉子節點一定是最后一行。所以要找深度最大的葉子節點。
- 那么如何找最左邊的呢？可以使用前序遍歷（當然中序，后序都可以，因為本題沒有中間節點的處理邏輯，只要左優先就行），保證優先左邊搜索，然后記錄深度最大的葉子節點，此時就是樹的最后一行最左邊的值。
解題步驟
- 確定遞歸函數的參數和返回值：參數必須有要遍歷的樹的根節點，還有就是一個int型的變量用來記錄最長深度。這里就不需要返回值了，所以遞歸函數的返回類型為void。本題還需要類里的兩個全局變量，maxLen用來記錄最大深度，result記錄最大深度最左節點的數值。
- 確定終止條件：當遇到葉子節點的時候，就需要統計一下最大的深度了，所以需要遇到葉子節點來更新最大深度。
- 確定單層遞歸的邏輯：在找最大深度的時候，遞歸的過程中依然要使用回溯。
代碼一：遞歸法

class Solution {
public:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {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;}
};

迭代法 ?

解題思路
- 只需要記錄最后一行第一個節點的數值就可以了。
代碼一：迭代法

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 記錄最后一行第一個元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

112.路徑總和

題目鏈接：112.路徑總和
文章講解：代碼隨想錄
113.路徑總和ii

遞歸法

解題思路
- 要遍歷從根節點到葉子節點的路徑看看總和是不是目標和。
- 可以使用深度優先遍歷的方式（本題前中后序都可以，無所謂，因為中節點也沒有處理邏輯）來遍歷二叉樹
解題步驟
- 確定遞歸函數的參數和返回類型：
- 參數：需要二叉樹的根節點，還需要一個計數器，這個計數器用來計算二叉樹的一條邊之和是否正好是目標和，計數器為int型。
- 返回值，遞歸函數什么時候需要返回值？什么時候不需要返回值？這里總結如下三點，本題并不要遍歷整棵樹，所以遞歸函數需要返回值，可以用bool類型表示。：
  - 如果需要搜索整棵二叉樹且不用處理遞歸返回值，遞歸函數就不要返回值。（113.路徑總和ii）
  - 如果需要搜索整棵二叉樹且需要處理遞歸返回值，遞歸函數就需要返回值。（二叉樹的最近公共祖先 (opens new window)）
  - 如果要搜索其中一條符合條件的路徑，那么遞歸一定需要返回值，因為遇到符合條件的路徑了就要及時返回。（本題的情況）
- 確定終止條件：首先計數器如何統計這一條路徑的和，不要去累加然后判斷是否等于目標和，代碼比較麻煩，可以用遞減，讓計數器count初始為目標和，然后每次減去遍歷路徑節點上的數值。如果最后count == 0，同時到了葉子節點的話，說明找到了目標和。如果遍歷到了葉子節點，count不為0，就是沒找到。
- 定單層遞歸的邏輯：因為終止條件是判斷葉子節點，所以遞歸的過程中就不要讓空節點進入遞歸了。遞歸函數是有返回值的，如果遞歸函數返回true，說明找到了合適的路徑，應該立刻返回
代碼一：遞歸法

class Solution {
private:bool traversal(TreeNode* cur, int count) {if (!cur->left && !cur->right && count == 0) return true; // 遇到葉子節點，并且計數為0if (!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 sum) {if (root == NULL) return false;return traversal(root, sum - root->val);}
};

迭代法

解題思路
- 使用棧模擬遞歸做回溯，此時棧里一個元素不僅要記錄該節點指針，還要記錄從頭結點到該節點的路徑數值總和。c++就我們用pair結構來存放這個棧里的元素。定義為：pair<TreeNode*, int> pair<節點指針，路徑數值>這個為棧里的一個元素。
代碼一：迭代法

class solution {public:bool haspathsum(TreeNode* root, int sum) {if (root == null) return false;// 此時棧里要放的是pair<節點指針，路徑數值>stack<pair<TreeNode*, int>> st;st.push(pair<TreeNode*, int>(root, root->val));while (!st.empty()) {pair<TreeNode*, int> node = st.top();st.pop();// 如果該節點是葉子節點了，同時該節點的路徑數值等于sum，那么就返回trueif (!node.first->left && !node.first->right && sum == node.second) return true;// 右節點，壓進去一個節點的時候，將該節點的路徑數值也記錄下來if (node.first->right) {st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));}// 左節點，壓進去一個節點的時候，將該節點的路徑數值也記錄下來if (node.first->left) {st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));}}return false;}
};

106.從中序與后序遍歷序列構造二叉樹

題目鏈接：106. 從中序與后序遍歷序列構造二叉樹 - 力扣（LeetCode）
文章講解：代碼隨想錄
105. 從前序與中序遍歷序列構造二叉樹 - 力扣（LeetCode）

遞歸法

解題思路
- 以后序數組的最后一個元素為切割點，先切中序數組，根據中序數組，反過來再切后序數組。一層一層切下去，每次后序數組最后一個元素就是節點元素。難點是如何切割。應該注意確定切割的標準，是左閉右開，還有左開右閉，還是左閉右閉，這個就是不變量，要在遞歸中保持這個不變量。
- 首先要切割中序數組，切割點在后序數組的最后一個元素，就是用這個元素來切割中序數組的，所以必要先切割中序數組。中序數組相對比較好切，找到切割點（后序數組的最后一個元素）在中序數組的位置，然后切割。
- 切割后序數組。首先后序數組的最后一個元素不能要，這是切割點也是當前二叉樹中間節點的元素，已經用了。后序數組沒有明確的切割元素來進行左右切割，不像中序數組有明確的切割點，切割點左右分開就可以了。此時有一個很重的點，就是中序數組大小一定是和后序數組的大小相同的。中序數組都切成了左中序數組和右中序數組了，那么后序數組就可以按照左中序數組的大小來切割，切成左后序數組和右后序數組。
- 中序數組切成了左中序數組和右中序數組，后序數組切割成左后序數組和右后序數組。接下來可以遞歸。
解題步驟
- 第一步：如果數組大小為零的話，說明是空節點了。
- 第二步：如果不為空，那么取后序數組最后一個元素作為節點元素。
- 第三步：找到后序數組最后一個元素在中序數組的位置，作為切割點
- 第四步：切割中序數組，切成中序左數組和中序右數組（順序別反，一定是先切中序數組）
- 第五步：切割后序數組，切成后序左數組和后序右數組
- 第六步：遞歸處理左區間和右區間
代碼一：二叉樹構造

class Solution {
private:TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {if (postorder.size() == 0) return NULL;// 后序遍歷數組最后一個元素，就是當前的中間節點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;}// 切割中序數組// 左閉右開區間：[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍棄末尾元素postorder.resize(postorder.size() - 1);// 切割后序數組// 依然左閉右開，注意這里使用了左中序數組大小作為切割點// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

（說明：基于代碼隨想錄課程學習，部分內容引用代碼隨想錄文章）