0.引言

• 112. 路徑總和
• 113.路徑總和ii
• 106.從中序與后序遍歷序列構造二叉樹
• 105.從前序與中序遍歷序列構造二叉樹

112. 路徑總和

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

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

示例 1：

image.png

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

示例 2：

image.png

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

示例 3：

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

提示：

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

Discussion | Solution

遞歸法

/*
 * @lc app=leetcode.cn id=112 lang=cpp
 *
 * [112] 路徑總和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     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:
  bool hasPathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) return false;
    return dfs(root, 0, targetSum);
  }

 private:
  // 這個只需要判斷有沒有，不許要返回值，可以使用前序遍歷，一旦找到了就返回,同樣左子樹右子樹的思想
  bool dfs(TreeNode* node, int sum, int& target) {
    if (node->left == nullptr && node->right == nullptr) {
      sum += node->val;
      if (sum == target) {
        return true;
      } else {
        return false;
      }
    }
    bool left = false, right = false;
    if (node->left) left = dfs(node->left, sum + node->val, target);
    if (node->right) right = dfs(node->right, sum + node->val, target);
    return right || left;
  }
};
// @lc code=end

113. 路徑總和 II

給你二叉樹的根節(jié)點 root 和一個整數(shù)目標和 targetSum ，找出所有 從根節(jié)點到葉子節(jié)點 路徑總和等于給定目標和的路徑。

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

示例 1：

image.png

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：[[5,4,11,2],[5,8,4,5]]

示例 2：

image.png

輸入：root = [1,2,3], targetSum = 5
輸出：[]

示例 3：

輸入：root = [1,2], targetSum = 0
輸出：[]

提示：

• 樹中節(jié)點總數(shù)在范圍 [0, 5000] 內
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Discussion | Solution

遞歸法

/*
 * @lc app=leetcode.cn id=113 lang=cpp
 *
 * [113] 路徑總和 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     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:
  vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    if (root == nullptr) return {};
    std::vector<std::vector<int>> res;
    dfs(root, {}, res, 0, targetSum);
    return res;
  }

 private:
  // 這個需要輸出值，需要全部遍歷完
  void dfs(TreeNode* node, std::vector<int> path,
           std::vector<std::vector<int>>& paths, int sum, int& target) {
    if (node->left == nullptr && node->right == nullptr) {
      sum += node->val;
      if (sum == target) {
        path.push_back(node->val);
        paths.push_back(path);
      }
      return;
    }
    // 這里path是vector就需要顯示回溯了,sum依然可以隱式回溯
    path.push_back(node->val);
    if (node->left) dfs(node->left, path, paths, sum + node->val, target);
    if (node->right) dfs(node->right, path, paths, sum + node->val, target);
    path.pop_back();
  }
};
// @lc code=end

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

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

示例 1:

image.png

輸入：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 中每一個值都在 inorder 中
• inorder 保證是樹的中序遍歷
• postorder 保證是樹的后序遍歷

Discussion | Solution

遞歸法

/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 從中序與后序遍歷序列構造二叉樹
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     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:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return build_tree(inorder, postorder);
  }

 private:
  // 左右子樹的思想,前序遍歷，從根節(jié)點開始分
  TreeNode* build_tree(std::vector<int>& inorder, std::vector<int>& postorder) {
    if (inorder.empty() && postorder.empty()) {
      return nullptr;
    }
    TreeNode* node = new TreeNode(postorder.back()); 
    int record_index = -1;
    for (int i = 0; i < inorder.size(); ++i) {
      if (inorder[i] == postorder.back()) {
        record_index = i;
        break;
      }
    }
    if (record_index == -1) return nullptr;
    // 注意初始化是左閉右開[inorder.begin(), inorder.begin() + record_index)
    std::vector<int> left_inorder(inorder.begin(), inorder.begin() + record_index);
    std::vector<int> left_postorder(postorder.begin(), postorder.begin() + record_index);
    std::vector<int> right_inorder(inorder.begin() + record_index + 1, inorder.end());
    std::vector<int> right_postorder(postorder.begin() + record_index, postorder.end() - 1);

    node->left = build_tree(left_inorder, left_postorder);     // 左
    node->right = build_tree(right_inorder, right_postorder);  // 右

    return node;
  }
};

105. 從前序與中序遍歷序列構造二叉樹

給定兩個整數(shù)數(shù)組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節(jié)點。

示例 1:

image.png

輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]

示例 2:

輸入: preorder = [-1], inorder = [-1]
輸出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 無重復 元素
• inorder 均出現(xiàn)在 preorder
• preorder 保證 為二叉樹的前序遍歷序列
• inorder 保證 為二叉樹的中序遍歷序列

Discussion | Solution

遞歸法

/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 從前序與中序遍歷序列構造二叉樹
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty()) {
            return nullptr;
        }
        return build_tree_dfs(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }

private:
    TreeNode* build_tree_dfs(vector<int>& preorder, int preorder_start, int preorder_end,
                             vector<int>& inorder, int inorder_start, int inorder_end) {
        if(preorder_start > preorder_end) {
            return nullptr;
        }
       
        TreeNode* root = new TreeNode(preorder[preorder_start]);// 前序的第一個數(shù)是根節(jié)點
        int cnt = 0;                                            // 統(tǒng)計左子樹元素個數(shù)
        for (int i = inorder_start; i <= inorder_end; i++) {    // 在后序遍中找到根節(jié)點
            if (inorder[i] == preorder[preorder_start]) {
            cnt = i - inorder_start;
            break;
            }
        }
        
        root->left = build_tree_dfs(preorder, preorder_start+1, preorder_start+cnt,
                                    inorder, inorder_start, inorder_start+cnt-1);
        root->right = build_tree_dfs(preorder, preorder_start+cnt+1, preorder_end,
                                     inorder, inorder_start+cnt+1, inorder_end);
        
        return root;
    }

};
// @lc code=end