1樓：碳酸鈉
實際上比較一下前序和中序的迴圈遍歷演算法就容易懂了：前序和中序的區別在於訪問結點的位置不同：前序是在入棧時訪問，而中序是在出棧時訪問。
具體來講，前序的訪問語句在每次壓棧時就會執行，中序的訪問語句在左子樹不斷壓棧，直到在最左處退棧時才執行，是不是符合印象中的遍歷順序？
正是因為前序和中序依附於同乙個棧，前中序便可唯一確定樹，而前後序就不能；中後序同理。
眾所周知，n個不同元素出棧序列的數量為C2n×1/(n+1)。假設該序列為a，b，c，d，其全部14種出棧序列分別對應前序為abcd的樹的乙個中序序列。這裡的邏輯誤區是不要以為abcd是一棵唯一的樹（顯然不是），abcd入棧的順序是唯一的，就是abcd，而出棧的時機卻可以是多種多樣的，不同的情形對應著不同的中序，僅此而已。
2樓：徐天天ZJ
遞迴地想這個問題。
乙個二叉樹的所有結點可作根結點與其子孫們組成子樹，在先序遍歷時，對於所有的子樹，其根結點入棧後，其左邊的子孫們方會入棧，這些子孫後於根結點入棧，故先於根結點出棧，而後才是根結點出棧並訪問其右子樹的結點們，同樣訪問完其右子樹的結點們亦出棧，因而得到的出棧順序裡，根結點的左子樹的結點們在其左邊，右子樹在其右側，這和中序遍歷的結果[1]是一樣的，由於上述對二叉樹的所有子樹均成立，故在先序遍歷一二叉樹時，棧的出棧順序即對之中序遍歷的結果。
可以舉個例子：
如圖的二叉樹，先序遍歷的結果和入棧順序都是是ABCDEFGHIJK，出棧的話對於A這個根結點，在遍歷時，其左子樹的結點B、C、D會先出棧，其右子樹的E、F···K會後出棧，得到的出棧順序便是[B、C、D]A[E、F···K]，其中以B為根結點的子樹同理，出棧順序為CBD，因而總的出棧順序便是[CBD]A[E、F···K][2]，同樣的[E、F···K]這個子樹出棧順序是[[F、G、H]E[I、J、K]]，E的子孫裡的子樹亦同理。
3樓：Hello World
首先三種遍歷方式在一棵樹上的「走法」是一致的（這個是三種遍歷方式規定的，都是左，左返回，根，右，右返回，不用證明），向下延伸，對應入棧（第一次經過某個節點）向上返回是出棧（第二次經過某個節點）；之後當我們使用前序遍歷時，也就是第一次經過該節點時就記錄，所以可以當做入棧；而中序遍歷時當第二次經過節點時記錄，所以是對應pop棧；
而對於後序遍歷，它將第二次遍歷得到的節點進行保留（不記錄），轉而繼續走這個節點的右子樹，但實際上這個節點已經走過兩次了，是應該pop掉，但是棧選擇保留，因為後序還需要遍歷右子樹，所以就會造成序列混亂
再次說明，前兩個計算方式都是第一次遍歷到push，第二次遍歷到pop，先序在push時輸出，中序在pop時輸出，而後序遍歷，第二次遍歷到該節點時沒有pop，而是選擇繼續遍歷，可以說是第三次才pop掉，所以它不滿足
4樓：甫清
因為前序遍歷和中序遍歷在用棧做遍歷的時候入棧順序是一樣的，而前序遍歷在入棧前訪問節點，中序遍歷是出棧時訪問節點，所以入棧後的節點什麼時候出棧都不影響前序遍歷的順序，而不同的出棧順序對應不同的中序遍歷結果，剛好對應了棧固定輸入順序得到的輸出結果，就可以用卡特蘭函式
我是這麼理解的，不知道有沒有啥問題
5樓：很鹹的鹹魚
對一棵樹或者子樹進行先序或者中序遍歷時入棧順序相同。
都是根節點、左子樹、右子樹，（注意是入棧）先序訪問後入棧，中序出棧後訪問，
則先序序列就是入棧順序，中序序列就是出棧順序。
6樓：幹總院
棧是先入後出
入棧的時候，如果是按先序遍歷
出棧的時候，該結點左右子樹已經出棧，而左右子樹先訪問，最後訪問本身，正是中序遍歷啊。
7樓：Yeeeeeee
你們全都誤解題主的意思了。
題主是說，為什麼可以把入棧次序看成二叉樹的前序遍歷次序，出棧次序看成二叉樹的中序遍歷次序，以此確定出來的二叉樹是合法的？
舉個例子吧。
那麼建立的樹就是
為什麼說「滿二叉樹也是完全二叉樹」？
一名 1 先明確完全二叉樹的概念。先上圖！完全二叉樹分為樓主所說的 圖1就是了 還有一種完全二叉樹是圖2。圖2也是完全二叉樹！圖2也是完全二叉樹！圖2也是完全二叉樹！概念 完全二叉樹分為兩種，1 最後一層沒有滿，那麼最後一層的節點都得在左邊。2 最後一層滿了，那就得全滿才行，圖2。完全二叉樹就這麼個...
為什麼說二叉樹遍歷用遞迴的方法不如非遞迴方法
薛瑄 雖然從時間複雜度來看，二叉樹遍歷遞迴和迭代都是O logn 但是這裡的常係數相差甚大。也就是說遞迴 O a Logn 迭代是O b Logn 這裡的a b 用鄧教授更通俗的說法是，1秒和1年都是O 1 但是他們的常係數相差甚遠。B樹和平衡二叉搜尋樹，查詢時間複雜度是O logn 但是常係數相差...
如何求二叉樹中某個指定節點的深度
刑事組之虎曹達華 遞迴求深度，傳入相應的節點即可 public static int treeDepth TreeNode root 計算左子樹的深度 int left treeDepth root.left 計算右子樹的深度 int right treeDepth root.right 樹root...