LeetCode Hot 100:二叉树
LeetCode Hot 100:二叉树
94. 二叉树的中序遍历
思路 1:递归
/**
* 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 {
private:
vector<int> ans;
public:
vector<int> inorderTraversal(TreeNode* root) {
helper(root);
return ans;
}
void helper(TreeNode* root) {
if (root == nullptr)
return;
helper(root->left);
ans.push_back(root->val);
helper(root->right);
}
};
104. 二叉树的最大深度
思路 1:递归
/**
* 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 maxDepth(TreeNode* root) {
return root ? max(maxDepth(root->left), maxDepth(root->right)) + 1 : 0;
}
};
思路 2:层序遍历
/**
* 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 maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
depth++;
}
return depth;
}
};
226. 翻转二叉树
思路 1:自底向上递归
/**
* 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* invertTree(TreeNode* root) {
if (root == nullptr)
return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
思路 2:自顶向下递归
/**
* 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* invertTree(TreeNode* root) {
if (root == nullptr)
return root;
TreeNode* l = invertTree(root->left);
TreeNode* r = invertTree(root->right);
root->left = r;
root->right = l;
return root;
}
};
101. 对称二叉树
思路 1:递归
/**
* 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 isSymmetric(TreeNode* root) {
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr)
return true;
if ((left && right == nullptr) || (left == nullptr && right))
return false;
if (left->val != right->val)
return false;
return isSymmetric(left->left, right->right) &&
isSymmetric(left->right, right->left);
}
};
思路 2:迭代
/**
* 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 isSymmetric(TreeNode* root) { return isSymmetric(root, root); }
bool isSymmetric(TreeNode* u, TreeNode* v) {
queue<TreeNode*> q;
q.push(u);
q.push(v);
while (!q.empty()) {
u = q.front();
q.pop();
v = q.front();
q.pop();
if (u == nullptr && v == nullptr)
continue;
if ((u && v == nullptr) || (u == nullptr && v))
return false;
if (u->val != v->val)
return false;
q.push(u->left);
q.push(v->right);
q.push(u->right);
q.push(v->left);
}
return true;
}
};
543. 二叉树的直径
思路 1:递归
/**
* 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 diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
function<int(TreeNode*)> dfs = [&](TreeNode* root) {
if (root == nullptr)
return 0;
int left = dfs(root->left);
int right = dfs(root->right);
ans = max(ans, left + right + 1);
return max(left, right) + 1;
};
dfs(root);
return ans - 1;
}
};
102. 二叉树的层序遍历
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr)
return {};
queue<TreeNode*> q;
q.push(root);
vector<vector<int>> ans;
while (!q.empty()) {
int sz = q.size();
vector<int> v;
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front();
q.pop();
v.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(v);
}
return ans;
}
};
108. 将有序数组转换为二叉搜索树
思路 1:递归
/**
* 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) {
return buildBST(nums, 0, nums.size() - 1);
}
TreeNode* buildBST(vector<int>& nums, int start, int end) {
if (start > end)
return nullptr;
int mid = start + (end - start) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildBST(nums, start, mid - 1);
root->right = buildBST(nums, mid + 1, end);
return root;
}
};
98. 验证二叉搜索树
思路 1:递归
/**
* 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) {
return isValidBST(root, LONG_LONG_MIN, LONG_LONG_MAX);
}
bool isValidBST(TreeNode* root, long long lower, long long upper) {
if (root == nullptr)
return true;
if (root->val <= lower)
return false;
if (root->val >= upper)
return false;
return isValidBST(root->left, lower, root->val) &&
isValidBST(root->right, root->val, upper);
}
};
思路 2:中序遍历
/**
* 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 {
private:
vector<int> arr;
public:
bool isValidBST(TreeNode* root) {
inOrder(root);
for (int i = 0; i < arr.size() - 1; i++)
if (arr[i] >= arr[i + 1])
return false;
return true;
}
void inOrder(TreeNode* root) {
if (root == nullptr)
return;
if (root->left)
inOrder(root->left);
arr.push_back(root->val);
if (root->right)
inOrder(root->right);
}
};
230. 二叉搜索树中第 K 小的元素
思路 1:中序遍历 + 辅助数组
/**
* 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 {
private:
vector<int> arr;
public:
int kthSmallest(TreeNode* root, int k) {
inOrder(root);
if (k > arr.size())
return -1;
return arr[k - 1];
}
void inOrder(TreeNode* root) {
if (root == nullptr)
return;
if (root->left)
inOrder(root->left);
arr.push_back(root->val);
if (root->right)
inOrder(root->right);
}
};
思路 2:中序遍历
/**
* 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 {
private:
int ans = 0;
public:
int kthSmallest(TreeNode* root, int k) {
inOrder(root, k);
return ans;
}
// 辅函数 - 中序遍历
void inOrder(TreeNode* root, int& k) {
if (root == nullptr)
return;
inOrder(root->left, k);
k--;
if (k == 0) {
ans = root->val;
return;
}
if (k > 0)
inOrder(root->right, k);
}
};
199. 二叉树的右视图
思路 1:层序遍历
/**
* 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:
vector<int> rightSideView(TreeNode* root) {
if (root == nullptr)
return {};
queue<TreeNode*> q;
q.push(root);
vector<int> ans;
while (!q.empty()) {
int sz = q.size();
vector<int> v;
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front();
q.pop();
v.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(v.back());
}
return ans;
}
};
114. 二叉树展开为链表
思路 1:先序遍历 + 辅助数组
/**
* 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 {
private:
vector<int> arr;
public:
void flatten(TreeNode* root) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr)
return;
preOrder(root);
root->left = nullptr;
root->right = nullptr;
TreeNode* p = root;
for (int i = 1; i < arr.size(); i++) {
TreeNode* node = new TreeNode(arr[i]);
p->right = node;
p = p->right;
}
}
void preOrder(TreeNode* root) {
if (root == nullptr)
return;
arr.push_back(root->val);
if (root->left)
preOrder(root->left);
if (root->right)
preOrder(root->right);
}
};
105. 从前序与中序遍历序列构造二叉树
思路 1:递归
/**
* 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
{
private:
unordered_map<int, int> index;
public:
// 主函数
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
int n = preorder.size();
// 构造哈希映射,帮助我们快速定位根节点
for (int i = 0; i < n; i++)
index[inorder[i]] = i;
return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
// 辅函数
TreeNode *buildTree(const vector<int> &preorder, const vector<int> &inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)
{
if (preorder_left > preorder_right)
return nullptr;
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode *root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树,并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = buildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树,并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = buildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
};
437. 路径总和 III
思路 1:递归
/**
* 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 pathSum(TreeNode* root, int targetSum) {
if (root == nullptr)
return 0;
int res = path_sum(root, targetSum);
res += pathSum(root->left, targetSum);
res += pathSum(root->right, targetSum);
return res;
}
long long path_sum(TreeNode* root, long long target) {
if (root == nullptr)
return 0LL;
long long count = root->val == target ? 1LL : 0LL;
target -= root->val;
count += path_sum(root->left, target);
count += path_sum(root->right, target);
return count;
}
};
思路 2:回溯 + 哈希表
/**
* 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 {
private:
unordered_map<long long, int> prefix; // <总和,次数>
public:
int pathSum(TreeNode* root, int targetSum) {
prefix[0] = 1; // 初始化
return backtrack(root, 0LL, targetSum);
}
// 辅函数
int backtrack(TreeNode* root, long long cur, int target) {
if (root == nullptr)
return 0;
int res = 0;
cur += root->val;
if (prefix.count(cur - target))
res += prefix[cur - target];
prefix[cur]++; // 修改当前节点状态
// 递归子节点
res += backtrack(root->left, cur, target);
res += backtrack(root->right, cur, target);
prefix[cur]--; // 回改当前节点状态
return res;
}
};
236. 二叉树的最近公共祖先
思路 1:递归
/**
* 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) {
if (root == nullptr)
return nullptr;
// p 和 q 其中有一个正好是 root,直接返回 root
if (root == p || root == q)
return root;
// 通过递归,得到左右两棵子树的值
TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
// p 和 q 分别在 root 的不同子树,直接返回 root
if (leftLCA && rightLCA)
return root;
// p 和 q 在 root 的同一侧,且 root 不等于 p 或者 q 的任何一个,那么就找 p 和 q 在的那一侧子树
return leftLCA == nullptr ? rightLCA : leftLCA;
}
};
124. 二叉树中的最大路径和
思路 1:递归
/**
* 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 maxPathSum(TreeNode* root) {
int ans = INT_MIN;
function<int(TreeNode*)> dfs = [&](TreeNode* root) -> int {
if (root == nullptr)
return 0;
int left = dfs(root->left);
int right = dfs(root->right);
int sum = root->val + left + right;
ans = max(ans, sum);
return max(max(left, right) + root->val, 0);
};
dfs(root);
return ans;
}
};