層序遍歷

層序遍歷是廣度優(yōu)先算法，需要隊列來實現(xiàn)。隊列先進先出符合一層層遍歷的邏輯，棧適合深度優(yōu)先算法是遞歸的邏輯。

先初始化，建立隊列和兩級數(shù)組。判斷頭節(jié)點是否為空，不為空則傳入隊列。邊界條件是隊列是否為空。循環(huán)內先初始化，size保存一層的元素個數(shù)，數(shù)組member保存元素數(shù)值。在一層內，每次彈出該層元素應當保存元素數(shù)值并存入其左右節(jié)點（如果存在）。最后將member存入兩級數(shù)組result中。

vector<vector<int>>?levelOrder(TreeNode*?root)?{

????????queue<TreeNode?*>?que;

????????vector<vector<int>>?result;

????????TreeNode?*Node;

????????if(root!=NULL)

????????????que.push(root);

????????while(!que.empty())

????????{

????????????int?size=que.size();

????????????vector<int>?member;

????????????for(int?i=0;i<size;i++)

????????????{

????????????????Node=que.front();

????????????????que.pop();

????????????????member.push_back(Node->val);

????????????????if(Node->left)?que.push(Node->left);

????????????????if(Node->right)?que.push(Node->right);

????????????}

????????????result.push_back(member);

????????}

????????return?result;

????}

完成了層序遍歷的十道練習題。

226.翻轉二叉樹

思路：

交換左右節(jié)點，再對左右節(jié)點進行遞歸。（前序）

看視頻后：

注意自己寫的是前序還是中序還是后序遍歷。這道題前序和后續(xù)都是類似的，但如果是中序需要注意 兩次遍歷都是對左子樹進行遍歷（模擬一下就明白了）

101. 對稱二叉樹

思路：

無思路。不能直接判斷左節(jié)點是否等于右節(jié)點。

看視頻后：

這道題的關鍵在于需要將左右節(jié)點的信息返回給中節(jié)點，所以需要后序遍歷：左右中。

單獨寫一個bool函數(shù)，列好情況：左空右非空（false），左非空右空(false)，左右空(true), 左右非空但值不同（false），左右非空但值相同（繼續(xù)遍歷）。當左右非空但值相同時，注意遍歷的是兩種情況，外側和內測。

????????????bool?outside=compare(left->left,right->right);

????????????bool?inside=compare(left->right,right->left);

????????????return?outside&&inside;

最后返回bool，并在主函數(shù)引用該函數(shù)。