首页 > 编程语言 >代码随想录算法训练营第十六天| 找树左下角的值

代码随想录算法训练营第十六天| 找树左下角的值

时间:2024-11-08 21:41:45浏览次数:5  
标签:right return int 找树 sum 随想录 左下角 root left

513.找树左下角的值

文章链接:https://programmercarl.com/0513.找树左下角的值.html
题目链接:https://leetcode.cn/problems/find-bottom-left-tree-value/description/

要点:不管是前中后序遍历,左节点总是先比右节点先遍历,所以只要找到深度最大的叶子节点,即找到最左下角的值

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) traversal(root->left,depth+1);
        if(root->right) traversal(root->right,depth+1);
    }
    int findBottomLeftValue(TreeNode* root) {
       traversal(root,1);
       return result;
    }
};

递归的方法:

class Solution {
public:
//迭代:层序遍历
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        int result;
        if(root!=NULL) que.push(root);
        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;
    }
};

路径总和

文章链接:https://programmercarl.com/0112.路径总和.html
题目链接:https://leetcode.cn/problems/path-sum/description/

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

路径总和II

题目链接:https://leetcode.cn/problems/path-sum-ii/description/

class Solution {
public:
    vector<vector<int>> result;
    void func(TreeNode* root,vector<int> path,int sum,int targetSum){
        path.push_back(root->val);
        sum+=root->val;
        if(root->left==NULL&&root->right==NULL){
            if(sum==targetSum) result.push_back(path);
        }
        if(root->left) func(root->left,path,sum,targetSum);
        if(root->right) func(root->right,path,sum,targetSum);
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==NULL) return{};
        vector<int> path;
        func(root,path,0,targetSum);
        return result;
    }
};

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

题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
文章链接:https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0) return NULL;
        //找到后序的最后一个元素,为根节点,进行分割
        int rootNum=postorder[postorder.size()-1];
        TreeNode* root=new TreeNode(rootNum);
        //叶节点
        if(postorder.size()==1) return root;
        //根据前序来分割,找到左右子树
        int index=0;
        for(index;index<inorder.size();index++){
            if(inorder[index]==rootNum) break;
        }
        vector<int> leftInorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightInorder(inorder.begin()+index+1,inorder.end());

        //根据前序左右子树的大小,分割后序序列
        vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());
        vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end()-1);
        //构造左子树
        root->left=buildTree(leftInorder,leftPostorder);
        root->right=buildTree(rightInorder,rightPostorder);
        return root;
    }
};

标签:right,return,int,找树,sum,随想录,左下角,root,left
From: https://www.cnblogs.com/VickyWu/p/18535983

相关文章

  • 代码随想录算法训练营day39 day40| 198.打家劫舍 213.打家劫舍II 337.打家劫舍III
    学习资料:https://programmercarl.com/0198.打家劫舍.html#算法公开课动态规划的打家劫舍系列和股票买卖系列(股票还有贪心算法可解)学习记录:198.打家劫舍(一维dp数组,前n间房子都可偷的情况下的最高金额,每间房子偷数都是由前一间和前两间决定)点击查看代码classSolution(object)......
  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的intg......
  • 代码随想录 -- 动态规划 -- 分割等和子集
    416.分割等和子集-力扣(LeetCode)思路:题目中表述:将数组nums分割成两个子集,使得两个子集的元素和相等。可以转化为:有一个背包,如果存在部分元素组合可以令容量为nums的和的一半的背包容纳的最大价值也为nums的和的一半,那么剩下的元素和也是nums的一半,则符合题意。dp[j]含义:......
  • 代码随想录算法训练营第二十一天| leetcode669. 修剪二叉搜索树、leetcode108.将有序
    1leetcode669.修剪二叉搜索树题目链接:669.修剪二叉搜索树-力扣(LeetCode)文章链接:代码随想录视频链接:你修剪的方式不对,我来给你纠正一下!|LeetCode:669.修剪二叉搜索树_哔哩哔哩_bilibili思路:目前想的是分三种情况,第一种情况就是这个数删除左边全部,第二种删除右边的全部,第......
  • 代码随想录算法训练营第三十九天|Day39 动态规划
    198.打家劫舍视频讲解:https://www.bilibili.com/video/BV1Te411N7SXhttps://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html思路#definemax(a,b)((a)>(b)?(a):(b))introb(int*nums,intnumsSize){if(numsSize==0){re......
  • 代码随想录算法训练营第四十天|Day40 动态规划
    121.买卖股票的最佳时机视频讲解:https://www.bilibili.com/video/BV1Xe4y1u77qhttps://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html思路#definemax(a,b)((a)>(b)?(a):(b))#definemin......
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先-力扣(LeetCode)文章链接:代码随想录视频链接:二叉搜索树找祖先就有点不一样了!|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路:用之前一样的方法,哈哈哈哈哈,好处就是做出来了,但是我觉得需......
  • 代码随想录算法训练营第九天|LeetCode151.翻转字符串里的单词、卡码网:55.右旋转字符串
    前言打卡代码随想录算法训练营第49期第九天︿( ̄︶ ̄)︿首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。今日题目LeetCode151翻转字......
  • 代码随想录算法训练营 day37 day38| 卡码网52.完全背包 518. 零钱兑换 II 377.
    学习资料:https://programmercarl.com/背包问题理论基础完全背包.html#算法公开课相比于01背包,完全背包中每个物品都可以无限次的放入组合:先遍历物品,再逆序遍历背包排列:先逆序遍历背包,再遍历物品学习记录卡码网52.携带研究资料(dp[i]代表当重量为i时的最大价值)点击查看代码n......
  • 代码随想录一刷day7 哈希表day1
    遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。常见三种实现哈希表的数据结构:数组set集合map映射下面是setmap的红黑树是一种平衡二叉搜索树,所以k......