代码随想录day18 二叉树开始各种方法尝试

发布时间:2024年01月03日

513.找树左下角的值

题目

给定一个二叉树,在树的最后一行找到最左边的值。

示例 1:

513.找树左下角的值

思考

本题用层序遍历就很好解,最后一层的第一个数,就是最后一行最左边的值,这里需要用一个二维vector把每一层的数都存下来

代码

class Solution {

public:

? ? int findBottomLeftValue(TreeNode* root) {

? ? ? ? queue<TreeNode*> que;

? ? ? ? vector<vector<int>> res;

? ? ? ? que.push(root);

? ? ? ? while(!que.empty()) {

? ? ? ? ? ? int size = que.size();

? ? ? ? ? ? vector<int> tmp;//把每一层都存起来,最后一层的第一个元素就是最底层最左边元素

? ? ? ? ? ? while(size--) {

? ? ? ? ? ? ? ? TreeNode* node = que.front();

? ? ? ? ? ? ? ? que.pop();

? ? ? ? ? ? ? ? tmp.push_back(node->val);

? ? ? ? ? ? ? ? if(node->left) que.push(node->left);

? ? ? ? ? ? ? ? if(node->right) que.push(node->right);

? ? ? ? ? ? }

? ? ? ? ? ? res.push_back(tmp);

? ? ? ? }

? ? ? ? return res[res.size()-1][0];

? ? }

};

112. 路径总和

题目

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树,以及目标和 sum = 22,

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思考

这题一看就是要用前序来做,但有个需要注意的点是需要用一个pair把结点和头结点到这个结点的和都存好,这样做的目的是在回溯中记录下每个结点的和,不然如果用int sum 的话在回溯过程中会出错,然后中左右的中是要判断该结点已经到底了并且和是否是targetSum。

代码

// ?前序遍历

class Solution {

public:

? ? bool hasPathSum(TreeNode* root, int targetSum) {

? ? ? ? stack<pair<TreeNode*, int>> stk;

? ? ? ? if(root == nullptr) return false;

? ? ? ? stk.push(pair<TreeNode*, int>(root,root->val));

? ? ? ? while(!stk.empty()) {

? ? ? ? ? ? pair<TreeNode*,int> node = stk.top();

? ? ? ? ? ? stk.pop();//这里是一个循环,压入一个回溯一个,要判断目前遍历的结点是否为叶子结点

? ? ? ? ? ? if(!node.first->left && !node.first->right && targetSum == node.second) return true;

? ? ? ? ? ? if(node.first->right) {

? ? ? ? ? ? ? ? stk.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));

? ? ? ? ? ? }

? ? ? ? ? ? if(node.first->left) {

? ? ? ? ? ? ? ? stk.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return false;

? ? }

};

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

题目

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

  • 中序遍历 inorder = [9,3,15,20,7]
  • 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

106. 从中序与后序遍历序列构造二叉树1

思考

初看有点蒙,感觉无从下手,看完卡哥视频才发现需要找到根结点,那么得从后序数组里找,最后一个数就是根结点,因为从左右中的顺序来说,中在最后,然后再中序数组中找到根结点,把其分为左右两个数组,同时根据中序数组的左右数组来确定后序数组的左右数组,因为左右数组的size都是相等的,这个技巧很关键,接着递归node->left、node->right就好,主要这里node->left、node->right是要等于递归的结果,而不是用if判断

代码

class Solution {

public:

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

? ? ? ? if (postorder.size() == 0) return nullptr;// 第一步:如果数组大小为零的话,说明是空节点了。

? ? ? ? int root = postorder[postorder.size() - 1];// 第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。

? ? ? ? TreeNode* node = new TreeNode(root);//新的treenode是这样创建

? ? ? ? int mid = 0;

? ? ? ? for(; mid < inorder.size(); mid++) {

? ? ? ? ? ? if(inorder[mid] == root) break;// 第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点

? ? ? ? }

? ? ? ? vector<int> leftInoroder(inorder.begin(), inorder.begin() + mid);

? ? ? ? vector<int> rightInorder(inorder.begin() + mid + 1, inorder.end());// 第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组,并且注意,这里要跳过mid,所以right数组是从mid+1开始)

? ? ? ? postorder.pop_back();

? ? ? ? vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInoroder.size());

? ? ? ? vector<int> rightPostorder(postorder.begin() + leftInoroder.size(), postorder.end());// 第五步:切割后序数组,切成后序左数组和后序右数组

? ? ? ? node->left = traversal(leftInoroder,leftPostorder);

? ? ? ? node->right = traversal(rightInorder, rightPostorder);// 第六步:递归处理左区间和右区间

? ? ? ? return node;

? ? }

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

? ? ? ? if(inorder.size() == 0 || postorder.size() == 0) return nullptr;

? ? ? ? return traversal(inorder, postorder);

? ? }

};

文章来源:https://blog.csdn.net/2301_80817427/article/details/135366810
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。