题目：513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1
题解：
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; } };
题目：112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
题解：
class Solution { private: bool traversal(TreeNode* cur, int count) { if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0 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 sum) { if (root == NULL) return false; return traversal(root, sum - root->val); } };
题目：106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 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 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
题解：
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); } };
