find-bottom-left-tree-value
給定一個(gè)二叉樹冲粤，在樹的最后一行找到最左邊的值。
閱讀
- 不懂最左值是什么意思爪瓜？
-
層次遍歷最大的最左的數(shù)值
理解有偏差：層次遍歷 利用隊(duì)列結(jié)構(gòu)蹬跃，第一個(gè)輸出的是root節(jié)點(diǎn)，pass
層次遍歷第一個(gè)輸出是2 不是1 二叉樹左子樹的左子樹左子樹的數(shù)值
理解有偏差：如果沒有左子樹只有右子樹呢 擴(kuò)展中序遍歷-
按照中序遍歷 第一個(gè)元素是最左數(shù)值嗎铆铆？
理解有偏差：
例子
第一個(gè)元素是4 中序遍歷時(shí)候層次最大的 第一輸出的元素就是結(jié)果
如果保證獲取的是5呢
中順第一個(gè)大于上層的元素就是當(dāng)前最大層最左的元素
最左-->中順遍歷第一個(gè)元素 -->同層次中序遍歷第一元素
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 一般性能優(yōu)化都是o(n2) ->o(n)->0(logn) 能不能在優(yōu)化
時(shí)間復(fù)雜度 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
