企业网站设计推荐,汕头网站建设模板,seo推广优化找stso88效果好,让路由器做网站服务器513. 找树左下角的值 给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1
思路#xff1a;找到最低层中最左侧的节点值#xff0c;比较适合层序遍历#xff0c;返回最…
513. 找树左下角的值 给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1
思路找到最低层中最左侧的节点值比较适合层序遍历返回最低层的第一个值即可。
细节判断是否是最低层需要保存节点的当前层数。可以用queuepair来保存pair保存节点指针层数
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {if(!root) return -1;queuepairTreeNode*,int q;q.push({root,1});int deepthMax1;int retroot-val;while(!q.empty()){pairTreeNode*,int pariFrontq.front();TreeNode* nodeFrontpariFront.first;int deepthpariFront.second;//判断是否是更低的一层if(deepthdeepthMax){deepthMaxdeepth;retnodeFront-val;}q.pop();if(nodeFront-left) q.push({nodeFront-left,deepth1});if(nodeFront-right) q.push({nodeFront-right,deepth1});}return ret;}
}; 时间复杂度O(n)其中 nnn 是二叉树的节点数目。 654. 最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。 示例 1 输入nums [3,2,1,6,0,5]
输出[6,3,5,null,2,0,null,null,1]
解释递归调用如下所示
- [3,2,1,6,0,5] 中的最大值是 6 左边部分是 [3,2,1] 右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 左边部分是 [] 右边部分是 [2,1] 。- 空数组无子节点。- [2,1] 中的最大值是 2 左边部分是 [] 右边部分是 [1] 。- 空数组无子节点。- 只有一个元素所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 左边部分是 [0] 右边部分是 [] 。- 只有一个元素所以子节点是一个值为 0 的节点。- 空数组无子节点。 思路最简单的方法是直接按照题目描述进行模拟。
左子树为 construct(nums,left,best−1)
右子树为 construct(nums,best1,right)
当递归到一个空数组时便可以返回一棵空的树。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findMaxIndex(vectorint nums){int ret0;for(int i1;inums.size();i){if(nums[i]nums[ret]) reti;}return ret;}TreeNode* constructMaximumBinaryTree(vectorint nums) {if(nums.empty()) return nullptr;int maxIndexfindMaxIndex(nums);vectorint leftNums(nums.begin(),nums.begin()maxIndex);vectorint rightNums(nums.begin()maxIndex1,nums.end());TreeNode* rootnew TreeNode(nums[maxIndex],constructMaximumBinaryTree(leftNums), //左子树constructMaximumBinaryTree(rightNums)); //右子树return root;}
}; 时间复杂度O(n^2)其中 nnn 是数组 nums\textit{nums}nums 的长度。在最坏的情况下数组严格递增或递减需要递归 n 层第 i (0≤in)层需要遍历 n−i个元素以找出最大值总时间复杂度为 O(n2)
思路2利用单调栈可以实现时间复杂度O(n)
代码随想录
