leetcode第513题-找树左下角的值
首先来来放松一下，思考一个问题 递归消耗空间吗？
好莱坞电影《盗梦空间》 提到一个六层空间在造梦的理论
这就是程序员中的递归呀
513. 找树左下角的值
1. 描述：
Given a binary tree, find the left most value in the last row of the tree.
给定一个二叉树，在树的最后一行找到最左边的值。
2. Example
示例 1:
输入:
2
/ \
1 3
遍历： [1] 2 [3]
输出:
1(最左的一个那个节点就是1 )示例 2:
输入：[1,2,3,4,null,5,6,null,null,7]
level
1 (1)
/ \ 2 3 (2)
/ / \ 4 5 6 (3)
/ 7 (4)
遍历： [4] 2 1 [7] 5 3 [6]
Output:
7( 第三层 最左的一个那个节是4， 第四层 最左的一个那个节是7)示例 3：
input：[1,null,2,null,3]
3.分析
期望结果：树的最大深度中最左的叶子节点。
变化因素：tree的深度是不确定的。
几个问题：
- 中序遍历时候 第一输出的元素就是结果 ?是错误的理解 ,
- 按照先顺遍历方式 对比输出顺序也是错误的 去掉节点 4和5 输出结果应该是 7 不是 3
- 中序遍历非递归可以实现吗？
- 复杂度：
递归方式 正确的理解 每个结点只遍历一次，时间复杂度O(1)，递归最多调用n次，空间复杂度O(n) 错误的理解： 每个节点访问一次 时间复杂度是o(n),需要一个遍历记录层次，空间复杂度0（1）， 消耗的空间少，时间多 非递归，使用栈，每个节点只需遍历一次，时间复杂度O(n)，使用栈，只需压入或弹出各一次，空间复杂度O(n)
4. c++
//递归遍历//执行用时: 16 ms, 在Find Bottom Left Tree Value的C++提交中击败了24.52% 的用户void findBottomLeftValue(TreeNode* root,int& depth,int level,int& result){ //递归结束条件
if (NULL ==root)
{ return ;
} //左子树访问完毕，在访问root节点
findBottomLeftValue(root->left,depth,level+1,result);
//非叶子节点，肯定不是最后一层的元素，
//同层的节点元素，最左面第一个元素最左的节点
if (level>depth && root->left ==NULL)
{
depth=level;
result=root->val;
}
findBottomLeftValue(root->right,depth,level+1,result);
}class Solution {public: //非递归遍历
//执行用时: 12 ms, 在Find Bottom Left Tree Value的C++提交中击败了40.11% 的用户
int findBottomLeftValue(TreeNode* root)
{
int ret = root->val; //
int height=0; int currentheight = height; queue<pair<TreeNode*, int>> q; //依赖队列，寻找历史足迹
q.push(make_pair(root, 1)); while (!q.empty())
{
height = q.front().second;
root = q.front().first; q.pop(); if (height > currentheight)
{
ret = root->val;
currentheight = height;
} if (root->left) q.push(make_pair(root->left, height+1)); if (root->right) q.push(make_pair(root->right, height+1));
} return ret;
}
};5. go
func findBottomLeftValue(root *TreeNode) int {
result:=0
depth:=0 //当前已经遍历过最大层次
find_bottom_left_value(root,1,&depth,&result) return result
}func find_bottom_left_value(root *TreeNode,level int,depth *int,result *int){ if root ==nil { return
}
find_bottom_left_value(root.Left,level+1,depth,result) //
if root.Left ==nil && level>*depth {
*depth=level
*result=root.Val
}
find_bottom_left_value(root.Right,level+1,depth,result)
}6 优化
执行用时: 16 ms →执行用时: 8 ms
这是为什么？ 我也不明白
class Solution {public: //执行用时: 8 ms, 在Find Bottom Left Tree Value的C++提交中击败了96.96% 的用户
int findBottomLeftValue(TreeNode* root)
{ int depth=0; int result=0;
findBottomLeftValue(root,depth,1,result); return result;
} void findBottomLeftValue(TreeNode* root,int& depth,int level,int& result)
{ //递归结束条件
if (NULL ==root)
{ return ;
} //非叶子节点，肯定不是最后一层的元素，
//同层的节点元素，最左面第一个元素最左的节点
if (root->left ==NULL &&level>depth )
{
depth=level;
result=root->val; //计算过程
}
//左子树访问完毕，在访问root节点
findBottomLeftValue(root->left,depth,level+1,result);
findBottomLeftValue(root->right,depth,level+1,result);
}
};哪种遍历方式最快【作业题】
二叉树每个节点都保存一个整数，想要求所有节点数值之和，哪种遍历方式最快？
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-01-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录