好莱坞电影《盗梦空间》 提到一个六层空间在造梦的理论
这就是程序员中的递归呀
Given a binary tree, find the left most value in the last row of the tree.
给定一个二叉树,在树的最后一行找到最左边的值。
示例 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]
期望结果:树的最大深度中最左的叶子节点。
变化因素:tree的深度是不确定的。
几个问题:
递归方式 正确的理解 每个结点只遍历一次,时间复杂度O(1),递归最多调用n次,空间复杂度O(n) 错误的理解: 每个节点访问一次 时间复杂度是o(n),需要一个遍历记录层次,空间复杂度0(1), 消耗的空间少,时间多 非递归,使用栈,每个节点只需遍历一次,时间复杂度O(n),使用栈,只需压入或弹出各一次,空间复杂度O(n)
//递归遍历//执行用时: 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;
}
};
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)
}
执行用时: 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);
}
};
二叉树每个节点都保存一个整数,想要求所有节点数值之和,哪种遍历方式最快?