LeetCode 热题 100 | 二叉树（一）

目录

1  基础知识

1.1  先序遍历

1.2  中序遍历

1.3  后序遍历

2  94. 二叉树的中序遍历

3  104. 二叉树的最大深度

4  226. 翻转二叉树

5  101. 对称二叉树

---

菜鸟做题，语言是 C++

1  基础知识

二叉树常见的遍历方式有：

• 先序遍历
• 中序遍历
• 后序遍历
• 深度优先遍历 = 先序遍历
• 广度优先遍历 = 层次遍历（后面有道题）

其实稍微观察一下就可以发现，“先序”、“中序”、“后序” 针对的是根节点的位置。即在 (根节点，左子树，右子树) 这个三元组中，根节点处于哪个位置。

1.1  先序遍历

1. 根节点
2. 根节点的左子树
3. 根节点的右子树

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

这个例子包括后面的两个例子，都是按照指定顺序遍历二叉树，同时将每个节点的值放入到容器 ans 中。

1.2  中序遍历

1. 根节点的左子树
2. 根节点
3. 根节点的右子树

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

1.3  后序遍历

1. 根节点的左子树
2. 根节点的右子树
3. 根节点

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

2  94. 二叉树的中序遍历

属于中序遍历（显然）

通过第 1 节的介绍，想必解决这个问题就很容易了。需要注意的是，我们的递归可以不需要返回值，因此需要额外写一个返回值为 void 的函数（但貌似你每次都返回一个 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. 翻转二叉树

属于先序遍历

解题思路：

1. 完成当前节点的翻转
2. 完成其左右子树的翻转

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 的函数，虽然递归期间的返回值都没有派上用场，但是最重要的是最后一个返回值，它返回的是整棵二叉树的根节点，符合本题对返回值的要求。

5  101. 对称二叉树

属于先序遍历；少有的参数需要传两个指针的题

解题思路：

1. 判断左右对称位置上的两个节点是否都存在
2. 判断这两个节点的值是否相等
3. 判断这两个节点的左右子树是否对称

思路说明图：

• 对称位置上的两个节点进行比较，即左侧的 “2” 和右侧的 “2”
• 左侧的 “2” 的左子树和右侧的 “2” 的右子树进行比较
• 左侧的 “2” 的右子树和右侧的 “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 中只有一方为空指针时，属于是非对称的情况。