線上程式設計介紹
阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：
https://developer.aliyun.com/coding本文為大家介紹其中的第35題：找出二叉搜尋樹的第2大的數 的題目解析，具體如下：
題目描述
等級：容易
知識點：樹
檢視題目：35題：找出二叉搜尋樹的第2大的數給定一個二叉搜尋樹，找出其第二大的數。
示例1
比如二叉搜尋樹如下
那麼第二大的值是25
注意
對于二叉搜尋樹，若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
解題思路
這是一個關于二叉搜尋樹的知識點。
對于二叉搜尋樹，若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
因為題中沒有說這是一棵平衡的樹，是以某些節點可能隻有一棵子樹。
對于樹中最大的數是很容易找到的，一直選擇右子樹直到右子樹為空就可以了。
對于第2大的數，存在兩種情況。一種是最大數的節點存在左子樹，一種是不存在左子樹。
第一種情況下。根據二叉搜尋樹的性質，可以知道25的左子樹中的所有值都比25小，也都比25的父節點（20）大。是以第二大的數應該出現在25的左子樹中。尋找25左子樹中的最大值即可。
第二種情況下。第二大的數就是最大數節點（60）的父節點（25）.因為25的父節點和左子樹都比25小。而右子樹中隻有最大數一個值。
對于特殊情況，根節點沒有右子樹。可以歸類到情況1中，根節點為最大的樹。如果也沒有左子樹的話，那就是樣例有問題了，因為這樣樹中隻有一個數。
時間複雜度O(n) 因為樹不是平衡的，是以最差的情況下，從根節點開始都隻有右子樹，需要完整周遊整棵樹。
空間複雜度O(1) 隻需要儲存目前周遊到的節點即可。
看完之後是不是有了想法了呢，快來練練手吧>>
檢視題目：找出二叉搜尋樹的第2大的數