目錄

1? 基礎知識

1.1? 先序遍歷

1.2? 中序遍歷

1.3? 后序遍歷

2? 94. 二叉樹的中序遍歷

3? 104. 二叉樹的最大深度

4? 226. 翻轉(zhuǎn)二叉樹

5? 101. 對稱二叉樹

---

菜鳥做題，語言是 C++

1? 基礎知識

二叉樹常見的遍歷方式有：

• 先序遍歷
• 中序遍歷
• 后序遍歷
• 深度優(yōu)先遍歷 = 先序遍歷
• 廣度優(yōu)先遍歷 = 層次遍歷（后面有道題）

其實稍微觀察一下就可以發(fā)現(xiàn)，“先序”、“中序”、“后序” 針對的是根節(jié)點的位置。即在 (根節(jié)點，左子樹，右子樹) 這個三元組中，根節(jié)點處于哪個位置。

1.1? 先序遍歷

1. 根節(jié)點
2. 根節(jié)點的左子樹
3. 根節(jié)點的右子樹

vector<int> ans;
void preorder(TreeNode* root) {if (!root) return;ans.push_back(root->val);preorder(root->left);preorder(root->right);
}

這個例子包括后面的兩個例子，都是按照指定順序遍歷二叉樹，同時將每個節(jié)點的值放入到容器 ans 中。

1.2? 中序遍歷

1. 根節(jié)點的左子樹
2. 根節(jié)點
3. 根節(jié)點的右子樹

vector<int> ans;
void inorder(TreeNode* root) {if (!root) return;inorder(root->left);ans.push_back(root->val);inorder(root->right);
}

1.3? 后序遍歷

1. 根節(jié)點的左子樹
2. 根節(jié)點的右子樹
3. 根節(jié)點

vector<int> ans;
void postorder(TreeNode* root) {if (!root) return;postorder(root->left);postorder(root->right);ans.push_back(root->val);
}

2? 94. 二叉樹的中序遍歷

屬于中序遍歷（顯然）

通過第 1 節(jié)的介紹，想必解決這個問題就很容易了。需要注意的是，我們的遞歸可以不需要返回值，因此需要額外寫一個返回值為 void 的函數(shù)（但貌似你每次都返回一個 vector<int> 也行得通）

class Solution {
public:void inorder(TreeNode* root, vector<int>& ans) {if (!root) return;inorder(root->left, ans);ans.push_back(root->val);inorder(root->right, ans);}vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;inorder(root, ans);return ans;}
};

3? 104. 二叉樹的最大深度

屬于后序遍歷：先獲得左右子樹的最大深度，再獲得本子樹的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;int leftMaxDepth = maxDepth(root->left);int rightMaxDepth = maxDepth(root->right);return 1 + max(leftMaxDepth, rightMaxDepth);}
};

精簡版：

class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;return 1 + max(maxDepth(root->left), maxDepth(root->right));}
};

4? 226. 翻轉(zhuǎn)二叉樹

屬于先序遍歷

解題思路：

1. 完成當前節(jié)點的翻轉(zhuǎn)
2. 完成其左右子樹的翻轉(zhuǎn)

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (!root) return nullptr;TreeNode * temp = root->right;root->right = root->left;root->left = temp;invertTree(root->left);invertTree(root->right);return root;}
};

這道題就沒有單獨寫一個返回值為 void 的函數(shù)，雖然遞歸期間的返回值都沒有派上用場，但是最重要的是最后一個返回值，它返回的是整棵二叉樹的根節(jié)點，符合本題對返回值的要求。

5? 101. 對稱二叉樹

屬于先序遍歷；少有的參數(shù)需要傳兩個指針的題

解題思路：

1. 判斷左右對稱位置上的兩個節(jié)點是否都存在
2. 判斷這兩個節(jié)點的值是否相等
3. 判斷這兩個節(jié)點的左右子樹是否對稱

思路說明圖：

• 對稱位置上的兩個節(jié)點進行比較，即左側(cè)的 “2” 和右側(cè)的 “2”
• 左側(cè)的 “2” 的左子樹和右側(cè)的 “2” 的右子樹進行比較
• 左側(cè)的 “2” 的右子樹和右側(cè)的 “2” 的左子樹進行比較

class Solution {
public:bool check(TreeNode * p, TreeNode * q) {if (!p && !q) return true;if (!p || !q) return false;return p->val == q->val &&check(p->left, q->right) && check(p->right, q->left);}bool isSymmetric(TreeNode* root) {return check(root->left, root->right);}
};

說明：

if (!p && !q) return true;
if (!p || !q) return false;

第一行判斷是指，當 p 和 q 都為空指針時，屬于是對稱的情況；第二行判斷是指，當 p 和 q 中只有一方為空指針時，屬于是非對稱的情況。