find-bottom-left-tree-value
给定一个二叉树,在树的最后一行找到最左边的值。
阅读
- 不懂最左值是什么意思?
-
层次遍历最大的最左的数值
层次遍历第一个输出是2 不是1
理解有偏差:层次遍历 利用队列结构,第一个输出的是root节点,pass
-
二叉树左子树的左子树左子树的数值
理解有偏差:如果没有左子树只有右子树呢 扩展中序遍历 -
按照中序遍历 第一个元素是最左数值吗?
理解有偏差:
例子
第一个元素是4 -
中序遍历时候层次最大的 第一输出的元素就是结果
中顺第一个大于上层的元素就是当前最大层最左的元素
最左-->中顺遍历第一个元素 -->同层次中序遍历第一元素
func findBottomLeftValue(root *TreeNode) int {
maxLevle := 0
leftValue := 0
findBottomValue(root, 1, &maxLevle, &leftValue)
return leftValue
}
func findBottomValue(root *TreeNode, level int, maxLevle *int, leftValue *int) {
if root == nil {
return
}
findBottomValue(root.Left, level+1, maxLevle, leftValue)
if level > *maxLevle {
*maxLevle = level
*leftValue = root.Val
}
findBottomValue(root.Right, level+1, maxLevle, leftValue)
}
Time Complexity : O(n)
Q1 一般性能优化都是o(n2) ->o(n)->0(logn) 能不能在优化
时间复杂度 o(n)
image.png
参考:
https://blog.csdn.net/fangjian1204/article/details/39179343
https://blog.csdn.net/u013904605/article/details/44596743?utm_source=blogxgwz0
题目
image.png
网友评论