問題一：實現(xiàn)二叉樹的先序、中序、后序遍歷，包括遞歸方式和非遞歸方式
對于遍歷序列，把打印節(jié)點值放在第一次訪問節(jié)點，就是先序遍歷；放在第二次訪問節(jié)點，就是中序遍歷；放在第三次訪問節(jié)點，就是后序遍歷
遞歸時每個節(jié)點都是訪問三次，關(guān)鍵是打印時機
非遞歸方式先序遍歷：準(zhǔn)備一個棧，先壓右邊的再壓左邊的
非遞歸方式中序遍歷：當(dāng)前節(jié)點為空，從棧彈出一個打印，彈出節(jié)點向右移動；若不為空壓入棧，入棧節(jié)點向左移動
非遞歸方式后序遍歷：先，中序遍歷只要做到訪問一個節(jié)點兩次，但后序要三次（參考遞歸方式），解決方法是用兩個棧，一個按中右左存入，另一個接受前一個的彈出，最后形成左右中
問題二：直觀打印一顆二叉樹（有空間感）
問題三：在二叉樹中找到一個節(jié)點的后繼節(jié)點
前驅(qū)節(jié)點：中序遍歷中每個節(jié)點的前一個節(jié)點；后繼節(jié)點：中序遍歷中每個節(jié)點的后一個節(jié)點
解決思路：如果一個節(jié)點沒有右節(jié)點，就找父節(jié)點并判斷這個節(jié)點是否為父節(jié)點的左孩子，不是繼續(xù)向上找，直到找到，返回此時的父節(jié)點；如果一個節(jié)點有右節(jié)點，就返回右節(jié)點子樹上最左的一個
問題四：二叉樹的序列化和反序列化
序列化：內(nèi)存中的二叉樹記錄到文本中，可以先序中序后序，或者按層序列化
先序方式序列化string:1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_(#表示空節(jié)點)
反序列化：按序列化反向生成二叉樹
問題五：這里視頻卡了沒看到
問題六：判斷一顆二叉樹是否平衡二叉樹，這個問題統(tǒng)屬于樹形dp，即二叉樹上的動態(tài)規(guī)劃
平衡二叉樹：一棵樹任何一個節(jié)點，左子樹與右子樹高度差不超過1
按照遞歸思路：①先看左數(shù)是否平衡，不平衡就返回結(jié)果，平衡記錄左數(shù)高度；②再看右數(shù)是否平衡，不平衡就返回結(jié)果，平衡記錄右數(shù)高度，設(shè)計遞歸函數(shù)時子樹判斷返回結(jié)果應(yīng)該包括（這棵樹是否平衡和子樹高度）
問題七：判斷一顆二叉樹是否搜索二叉樹、完全二叉樹
搜索二叉樹：一棵樹上任何一個節(jié)點，左子樹節(jié)點都比它小，右子樹節(jié)點都比它大，即中序遍歷升序排列，通常節(jié)點是不重復(fù)的
完全二叉樹：二叉樹按層遍歷①一個節(jié)點有右節(jié)點沒有左節(jié)點，返回false②一個節(jié)點不是左右節(jié)點均存在（兩種情況，有左沒右或者都沒有），它后面遇到的節(jié)點都必須是葉節(jié)點
tip：用二叉樹實現(xiàn)堆沒有擴容代價（例如vector容量不夠空間翻倍），二叉樹只是一個節(jié)點一個節(jié)點的加
問題八：一顆完全二叉樹求節(jié)點個數(shù)，要求時間復(fù)雜度低于O(N)
對于滿二叉樹高度為l，節(jié)點個數(shù)為2^l-1，①先找到一個節(jié)點的左邊界（O(logN)），這樣可以計算出左邊界的高度，然后遍歷右子樹的左邊界，觀察右子樹的左邊界是否到了相同層數(shù)，到了那么整個左子樹都是滿的；計算2^層數(shù)=左子樹加這個節(jié)點的數(shù)目，然后對這個節(jié)點的右子樹按上述方式遞歸
②如果右子樹的左邊界沒有到相同層數(shù)，那么暗示右子樹是滿的，計算2^（層數(shù)-1）=右子樹加這個節(jié)點的數(shù)目，然后對左子樹繼續(xù)遞歸
這樣每一層都只找一個節(jié)點，復(fù)雜度為O(logN)，找右子樹左邊界也是O(logN)，最終時間復(fù)雜度為O(logN)*O(logN)
