樹相關個人刷題總結

​​589 N叉樹的前序周遊​​

​​144 二叉樹的前序周遊​​

​​98 驗證二叉搜尋樹​​

​​102 二叉樹的層序周遊​​

589 N叉樹的前序周遊

難度，簡單

法一，遞歸

法二，正常疊代，借助棧

144 二叉樹的前序周遊

遞歸就不說了，這裡附上非遞歸代碼

98 驗證二叉搜尋樹

中等

方法一：先中序周遊，得到一個序列，看該序列是否是遞增的，屬于正常思路

方法二：

每一個節點的值 需要在lower 和 upper之間，周遊左子樹時upper為根節點，周遊右子樹時，lower為根節點 參考自官方題解

102 二叉樹的層序周遊

方法一，借助隊列的兩種寫法，寫法一是自己的做法

兩種寫法的思路是一樣的，都是借助隊列，不過我的寫法是把非空節點入隊，寫法二是一股腦都入隊，出隊的時候再進行判斷

8ms11.7MB

寫法二是參考題解稍作改進

4ms 11.8MB

方法二： 深度優先，上面的方法一是廣度優先

但是正常來說，廣度優先是順着一條路走到底，然後再回頭，這和先序周遊很像

但是這裡怎麼才能知道哪些節點是在同一層呢，通過變量level進行标記