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

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

时间:2024-05-27 10:44:45浏览次数:28  
标签:node 第十八天 right return val 随想录 左下角 root left

513.找树左下角的值

题目链接 文章讲解 视频讲解

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    int findBottomLeftValue(TreeNode* root) {       
        int depth = 0;
        traversal(root, depth);
        return result;
    }
    void traversal(TreeNode* node, int depth) {
        if(node->left == nullptr && node->right == nullptr) {
            if(maxDepth < depth) {
                maxDepth = depth;
                result = node->val;
            }
            return ;
        }
        if(node->left) {
            depth++;
            traversal(node->left, depth);
            depth--;
        } 
        if(node->right) {
            depth++;
            traversal(node->right, depth);
            depth--;
        }
    }
};

112.路径总和

题目链接 文章讲解 视频讲解

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

113.路经总和II

题目链接

class Solution {
private:
    int total = 0;
    vector<vector<int>> ans;
    vector<int> path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return {};
        path.push_back(root->val);
        total += root->val;
        traversal(root, targetSum);
        return ans;
    }
    void traversal(TreeNode* node, int targetSum) {
        if(node->left == nullptr && node->right == nullptr) {
            if(total == targetSum) ans.push_back(path);
            return ;
        }
        if(node->left) {
            path.push_back(node->left->val);
            total += node->left->val;
            traversal(node->left, targetSum);
            total -= node->left->val;
            path.pop_back();
        } 
        if(node->right) {
            path.push_back(node->right->val);
            total += node->right->val;
            traversal(node->right, targetSum);
            total -= node->right->val;
            path.pop_back();
        } 
        return ;
    }
};

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        // 后序或者前序数组为空时,直接返回空
        if(postorder.size() == 0) return nullptr;
        if(postorder.size() == 1) {
            // 构造根节点
            TreeNode* root = new TreeNode(postorder[0]);    
            return root;
        }
        TreeNode * root = new TreeNode();
        root->val = postorder.back();

        // 切中序数组
        int idx = 0;
        for(; idx < inorder.size(); ++idx) {
            if(inorder[idx] == root->val)
                break;
        }
        // 左中序
        vector<int> left_inorder(inorder.begin(), inorder.begin() + idx);
        // 右中序
        vector<int> right_inorder(inorder.begin() + idx + 1, inorder.end());

        // 切后序数组
        // 左后序
        vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
        // 右后序
        vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1);

        // 递归构建左子树
        root->left = buildTree(left_inorder, left_postorder);
        // 递归构建右子树
        root->right = buildTree(right_inorder, right_postorder);

        return root;
    }
};

标签:node,第十八天,right,return,val,随想录,左下角,root,left
From: https://www.cnblogs.com/cscpp/p/18215045

相关文章

  • 代码随想录算法训练营第三天 |203、707、206
    链表基础理论:https://programmercarl.com/链表理论基础.html203题目链接:https://leetcode.cn/problems/remove-linked-list-elements/203代码随想录:https://programmercarl.com/0203.移除链表元素.html#算法公开课707题目链接:https://leetcode.cn/problems/design-linked-lis......
  • 代码随想录算法训练营第第18天 | 513.找树左下角的值 、112. 路径总和 、106.从中
    找树左下角的值本地递归偏难,反而迭代简单属于模板题,两种方法掌握一下题目链接/文章讲解/视频讲解:https://programmercarl.com/0513.找树左下角的值.html/***Definitionforabinarytreenode.*functionTreeNode(val,left,right){*this.val=(val===undef......
  • Day36 代码随想录打卡|二叉树篇---翻转二叉树
    题目(leecodeT226):给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。方法:迭代法翻转二叉树,即从根节点开始,一一交换每个节点的左右孩子节点,然后递归此过程,将根节点的左右孩子节点再分别作为参数传入交换节点的函数中。重复此过程,直到结束。就完成了二叉树的翻......
  • 代码随想录算法训练营第三十七天|435. 无重叠区间、763.划分字母区间、56. 合并区间、
    435.无重叠区间文档讲解:代码随想录题目链接:.-力扣(LeetCode)本道题与上个题目相似,都是求重叠区间统计重叠区间的个数,减去重叠区间的个数就是无重叠区间了主要就是为了让区间尽可能的重叠。(为什么)按照左边界排序①如果i的左边界大于等于上一个区间的右边界,就没有重叠......
  • 代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度、111.二
    104.二叉树的最大深度题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/文档讲解:https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE......
  • 代码随想录算法训练营第36期DAY38
    DAY38435无重叠区间昨晚很快就想出来了,今天相当于二刷。class Solution {public:    static bool mycmp(vector<int>&a,vector<int>&b){        return a[1]<b[1];    }    int eraseOverlapIntervals(vector<vector<int>>& intervals) {   ......
  • 代码随想录算法训练营第36期DAY39
    道心破碎的一天,继续加油吧,坚持努力。DAY39738单调递增的数字暴力法:没有想到用inti=n;i>0;i--来遍历。class Solution {private:    bool checknum(int num){        if(num<10) return true;        while(num/10!=0){           ......
  • 代码随想录算法训练营第36期DAY37
    DAY37先二刷昨天的3道题目,每种方法都写:是否已完成:是。报告:134加油站的朴素法没写对。原因是:在if中缺少了store>=0的判断,只给出了index==i的判断。前进法没写出来。因为忘记了总油量的判断。Sum。注意变量的初始化。分配糖果注意if里面放的是ratings;860柠檬水找零网上摘得思......
  • 代码随想录——二叉树的所有路径(Leetcode257)需要回顾
    题目链接BFS+队列维护一个队列,存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中,我们取出队列中的首节点,如果它是叶子节点,则将它对应的路径加入到答案中。如果它不是叶子节点,则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜......
  • 代码随想录算法训练营第一天 | 977.有序数组的平方;
    代码随想录算法训练营第一天|977.有序数组的平方;977题链接:https://leetcode.cn/problems/squares-of-a-sorted-array/代码随想录链接:https://programmercarl.com/0977.有序数组的平方.html#思路209题链接:https://leetcode.cn/problems/minimum-size-subarray-sum/submission......