Leetcode 513-找树左下角的值

题目描述

https://leetcode.cn/problems/find-bottom-left-tree-value/

解题思路

我们要找的是深度最大的叶子节点

这道题用层序遍历相对更简单，层序遍历（迭代法）在遍历过程中记录最后一行的第一个节点的数值：

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != nullptr) 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;}
};

递归法：

class Solution {
public:int maxDepth = INT_MIN;//正确处理边界，保证当前最大深度对应的result正确更新int result;int tranversal(TreeNode* root, int depth) {if (root->left == nullptr && root->right == nullptr) {if (depth > maxDepth) {maxDepth = depth;result = root->val;}return 0;}if (root->left) {depth++;tranversal(root->left, depth);depth--;}if (root->right) {depth++;tranversal(root->right, depth);}return 0;}int findBottomLeftValue(TreeNode* root) {tranversal(root, 0);return result;}
};

Leetcode 112-路径总和

题目描述

https://leetcode.cn/problems/path-sum/description/

解题思路

采用递归的方法，在处理过程中没有对“中”的处理，因此本题中前中后序算法是类似的。

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

相关题目

Leetcode 113-路径总和 ii

https://leetcode.cn/problems/path-sum-ii/description/

class Solution {
private:vector<vector<int>>result;vector<int> temp;void tranversal(TreeNode* cur, int count) {if (cur->left == nullptr && cur->right == nullptr && count == 0) {result.push_back(temp);return;}if (cur->left == nullptr && cur->right == nullptr)return;if (cur->left) {//如果左节点不为空temp.push_back(cur->left->val);tranversal(cur->left, count - cur->left->val);temp.pop_back();}if (cur->right) {//如果右节点不为空temp.push_back(cur->right->val);tranversal(cur->right, count - cur->right->val);temp.pop_back();}return;}
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {result.clear();temp.clear();if (root == nullptr)return result;temp.push_back(root->val);tranversal(root, targetSum - root->val);return result;}
};

Leetcode 106-从中序与后序遍历序列构造二叉树

题目描述

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

解题思路

后序最后一个节点是根节点，然后通过中序完成根节点左右节点的切割。之后的节点划分类似。

整体思路：

1. 后序数组为 0，空节点；
2. 后序数组最后一个元素为节点元素；
3. 寻找中序数组位置作切割点；
4. 切中序数组；
5. 切后序数组；
6. 递归处理左区间右区间

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, 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 index = 0;for (index; index < inorder.size(); index++) {//用中节点切割中序if (inorder[index] == rootValue)break;}vector<int> leftInorder(inorder.begin(), inorder.begin() + index);//左中序vector<int>rightInorder(inorder.begin() + index + 1, inorder.end());//右中序int length = leftInorder.size();vector<int>leftPostorder(postorder.begin(), postorder.begin() + length);//左后序vector<int>rightPostorder(postorder.begin() + length, postorder.end() - 1);//右后序root->left = buildTree(leftInorder, leftPostorder);root->right = buildTree(rightInorder, rightPostorder);return root;}
};

类似题目

Leetcode 105-从前序与中序遍历序列构造二叉树

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.size() == 0) return nullptr;int rootValue = preorder[0];TreeNode* root = new TreeNode(rootValue);if (preorder.size() == 1) return root;int index = 0;for (index; index < inorder.size(); index++) {if (inorder[index] == rootValue)break;}vector<int> leftInorder(inorder.begin(), inorder.begin() + index);//左中序vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());//右中序int length = leftInorder.size();vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + length);//中左序vector<int> rightPreorder(preorder.begin() + 1 + length, preorder.end());//中右序root->left = buildTree(leftPreorder, leftInorder);root->right = buildTree(rightPreorder, rightInorder);return root;}
};

前面两道题分别考察了中序和前序、中序和后序确定构建二叉树，但后序和前序不能确定唯一的一棵二叉树，因为不能确定左右区间的分割点。