重点解决 LeetCode 中 List 为 Top Interview Questions 且 Tag 为 Binary Tree 的题目。
1 二叉树的遍历（常规形式）
题意
给出二叉树的前序（Pre-Order）、中序（In-Order）、后序（Post-Order）遍历的递归、循环实现。
C++ 实现
递归版本：
void traversal(TreeNode *root, vector<int> &path) {
if (!root) return nullptr;
path.push_back(root->val);
traversal(root->left, path);
traversal(root->right, path);
traversal(root->left, path);
path.push_back(root->val);
traversal(root->right, path);
traversal(root->left, path);
traversal(root->right, path);
path.push_back(root->val);
}
|
循环版本：
vector<int> traversal(TreeNode* root) {
vector<int> path = {};
stack<pair<TreeNode*, bool>> s;
s.push({root, false});
while (!s.empty()) {
const auto p = s.top(); s.pop();
TreeNode* node = p.first;
bool visited = p.second;
if (!node) continue;
if (visited) {
path.push_back(node->val);
} else {
s.push({node->right, false});
s.push({node->left, false});
s.push({node, true});
s.push({node->right, false});
s.push({node, true});
s.push({node->left, false});
s.push({node, true});
s.push({node->right, false});
s.push({node->left, false});
}
}
return path;
}
|
2 二叉树的层级遍历
LeetCode 102. Binary Tree Level Order Traversal
题意
给出二叉树的层级（Level）遍历的循环实现，同一层的元素放在同一个数组里，不同层的元素放在不同的数组里。
C++ 实现
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res = {};
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
queue<TreeNode*> tq;
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (!node) continue;
level.push_back(node->val);
tq.push(node->left);
tq.push(node->right);
}
if (!level.empty()) res.push_back(level);
q = tq;
}
return res;
}
|
3 二叉树的之字形遍历
LeetCode 103. Binary Tree Zigzag Level Order Traversal
题意
给出二叉树的之字形（Zigzag）遍历的循环实现，同一层的元素放在同一个数组里，不同层的元素放在不同的数组里。
C++ 实现
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res = {};
stack<TreeNode*> s;
s.push(root);
int cnt = 0;
while (!s.empty()) {
vector<int> level;
stack<TreeNode*> ts;
while (!s.empty()) {
TreeNode* node = s.top(); s.pop();
if (!node) continue;
level.push_back(node->val);
if (cnt % 2 == 0) {
ts.push(node->left);
ts.push(node->right);
} else {
ts.push(node->right);
ts.push(node->left);
}
}
if (!level.empty()) res.push_back(level);
s = ts;
++cnt;
}
return res;
}
|
4 根据前序遍历和中序遍历构造二叉树
LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal
题意
以数组形式给定二叉树的前序遍历和中序遍历，构造出该二叉树的数据结构。
思路
根据前序遍历的定义，preorder 的第 0 个元素 preorder[0]，必然是整个二叉树的根节点，构造该节点。
根据中序遍历的定义，preorder[0] 在 inorder 中的位置，其左侧所有元素会构成根节点的左子树，其右侧所有元素会构成根节点的右子树。
接着 preorder 的第 1 个元素 preorder[1]，必然是左子树的根节点，构造该节点，其在 inorder 中的位置，左侧构成左子树的左子树，右侧构成左子树的右子树。
不断重复上述过程，便可不断构造子树。
C++ 实现
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size(), pre_idx = 0;
for (int i = 0; i < n; ++i) {
inorder_val2idx[inorder[i]] = i;
}
return build(preorder, inorder, pre_idx, 0, n-1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder,
int& pre_idx, int in_beg, int in_end) {
if (in_beg > in_end) return nullptr;
TreeNode* root = new TreeNode(preorder[pre_idx]);
int in_idx = inorder_val2idx[preorder[pre_idx]];
++pre_idx;
root->left = build(preorder, inorder, pre_idx, in_beg, in_idx-1);
root->right = build(preorder, inorder, pre_idx, in_idx+1, in_end);
return root;
}
private:
unordered_map<int, int> inorder_val2idx = {};
};
|
5 根据中序遍历和后序遍历构造二叉树
LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal
题意
以数组形式给定二叉树的前序遍历和中序遍历，构造出该二叉树的数据结构。
思路
与前一题的思路一致，不再赘述。
C++ 实现
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size(), post_idx = n-1;
for (int i = 0; i < n; ++i) {
inorder_val2idx[inorder[i]] = i;
}
return build(inorder, postorder, 0, n-1, post_idx);
}
TreeNode* build(vector<int>& inorder, vector<int>& postorder,
int in_beg, int in_end, int& post_idx) {
if (in_beg > in_end) return nullptr;
TreeNode* root = new TreeNode(postorder[post_idx]);
int in_idx = inorder_val2idx[postorder[post_idx]];
--post_idx;
root->right = build(inorder, postorder, in_idx+1, in_end, post_idx);
root->left = build(inorder, postorder, in_beg, in_idx-1, post_idx);
return root;
}
private:
unordered_map<int, int> inorder_val2idx = {};
};
|
6 找出二叉树中两个节点的最小公共父节点
LeetCode 236. Lowest Common Ancestor of a Binary Tree
题意
给定二叉树，找出其中两个节点的最小公共父节点。
思路
对二叉树进行遍历，过程中不断判断，当前节点及左右子树是否包含 p 和 q，如果同时满足，则记录该节点，记录一次之后不再记录，保证记录的为最小公共子节点。
C++ 实现
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* res = nullptr;
auto ret = travel(root, p, q, res);
return res;
}
pair<bool, bool> travel(TreeNode* node, TreeNode* p, TreeNode* q, TreeNode* &res) {
if (!node || res) return {false, false};
auto left_ret = travel(node->left, p, q, res);
auto right_ret = travel(node->right, p, q, res);
bool p_hit = (node == p) || left_ret.first || right_ret.first;
bool q_hit = (node == q) || left_ret.second || right_ret.second;
if (p_hit && q_hit && !res) {
res = node;
}
return {p_hit, q_hit};
}
};
|
7 验证是否为二叉搜索树
LeetCode 98. Validate Binary Search Tree
题意
给定二叉树，判断是否为二叉搜索树。
思路
根据二叉搜索树的定义，对于任意一个节点：
C++ 实现
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
auto p = is_valid(root);
return p.first;
}
pair<bool, pair<int, int>> is_valid(TreeNode* node) {
if (!node->left && !node->right) {
return {true, {node->val, node->val}};
}
int node_min = node->val, node_max = node->val;
if (node->left) {
auto p = is_valid(node->left);
bool valid = p.first;
auto [left_min, left_max] = p.second;
if (valid && left_max < node->val) {
node_min = left_min;
} else {
return {false, {0, 0}};
}
}
if (node->right) {
auto p = is_valid(node->right);
bool valid = p.first;
auto [right_min, right_max] = p.second;
if (valid && right_min > node->val) {
node_max = right_max;
} else {
return {false, {0, 0}};
}
}
return {true, {node_min, node_max}};
}
};
|
上述实现的难点在于辅助函数 is_valid 返回类型的设计，pair<bool, pair<int, int>> 的含义对应：以 node 为根节点的树是否为二叉搜索树、以 node 为根节点的树的最小值和最大值。
8 根据有序数组构造二叉搜索树
LeetCode 108. Convert Sorted Array to Binary Search Tree
题意
给定有序数组，由此构造一个平衡的二叉搜索树，平衡是指任一节点的左右子树的深度之差总不超过 1。
思路
不断二分，将中位数构造为根节点，其左侧递归构造左子树，其右侧递归构造右子树。
C++ 实现
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int n = nums.size();
return build(nums, 0, n-1);
}
TreeNode* build(vector<int>& nums, int beg, int end) {
if (beg > end) return nullptr;
int mid = beg + (end - beg) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = build(nums, beg, mid-1);
node->right = build(nums, mid+1, end);
return node;
}
};
|
9 找出二叉搜索树中第 K 小的元素
LeetCode 230. Kth Smallest Element in a BST
题意
给定二叉搜索树，找出其中第 K 小的元素（从 1 开始计数）。
思路
对二叉搜索树进行中序遍历，从而实现从小到大进行遍历，过程中计数，到 K 则记录节点的值。
C++ 实现
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int order = 1, val = 0;
travel(root, k, order, val);
return val;
}
void travel(TreeNode* node, int k, int& order, int& val) {
if (!node) return;
travel(node->left, k, order, val);
if (order++ == k) val = node->val;
if (order > k) return;
travel(node->right, k, order, val);
}
};
|