面试中常见的二叉树题目汇总

重点解决 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;
// Pre-Order
path.push_back(root->val);
traversal(root->left, path);
traversal(root->right, path);
// In-Order
traversal(root->left, path);
path.push_back(root->val);
traversal(root->right, path);
// Post-Order
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 {
// Pre-Order
s.push({node->right, false});
s.push({node->left, false});
s.push({node, true});
// In-Order
s.push({node->right, false});
s.push({node, true});
s.push({node->left, false});
// Post-Order
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++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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

题意

给定二叉树,找出其中两个节点的最小公共父节点。

思路

对二叉树进行遍历,过程中不断判断,当前节点及左右子树是否包含 pq,如果同时满足,则记录该节点,记录一次之后不再记录,保证记录的为最小公共子节点。

C++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
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++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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++ 实现

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
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);
}
};