首页 技术 正文
技术 2022年11月24日
0 收藏 391 点赞 2,639 浏览 6138 个字

最近在做LeetCode上面有关二叉树的题目,这篇博客仅用来记录这些题目的代码。

二叉树的题目,一般都是利用递归来解决的,因此这一类题目对理解递归很有帮助。

1.Symmetric Tree(https://leetcode.com/problems/symmetric-tree/description/)

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

2.Binary Tree Level Order Traversal(https://leetcode.com/problems/binary-tree-level-order-traversal/description/)

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int layer_size = q.size();
vector<int> layer;
for (int i = ; i < layer_size; i++) {
TreeNode *temp = q.front();
q.pop();
layer.push_back(temp->val);
if (temp->left != NULL) q.push(temp->left);
if (temp->right != NULL) q.push(temp->right);
} }
return res;
}
};

3.Binary Tree Level Order Traversal II(https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/)

class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return res;
vector<int> layer;
queue<TreeNode*> q;
q.push(root);
int count = ;
while (!q.empty()) {
TreeNode* temp = q.front();
q.pop();
count--;
layer.push_back(temp->val);
if (temp->left != NULL) q.push(temp->left);
if (temp->right != NULL) q.push(temp->right);
if (count == ) {
count = q.size();
res.push_back(layer);
layer.clear();
}
}
for (int i = ; i < res.size() / ; i++) {
vector<int> temp = res[i];
res[i] = res[res.size() - i - ];
res[res.size() - i - ] = temp;
}
return res;
}
};

4.Same Tree(https://leetcode.com/problems/same-tree/description/)

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

5.Path Sum(https://leetcode.com/problems/path-sum/description/)

class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
if (root->left == NULL && root->right == NULL && sum == root->val) return true;
else return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};

6.Path Sum II(https://leetcode.com/problems/path-sum-ii/description/)

class Solution {
public:
void helper(TreeNode *root, vector<vector<int>>& res, vector<int> t, int sum) {
if (root == NULL) return;
if (sum - root->val == && root->left == NULL && root->right == NULL) {
t.push_back(root->val);
res.push_back(t);
}
else if (root->left == NULL && root->right == NULL) {
return;
}
else {
t.push_back(root->val);
helper(root->left, res, t, sum - root->val);
helper(root->right, res, t, sum - root->val);
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if (root == NULL) return res;
vector<int> t;
helper(root, res, t, sum);
return res;
}};

7.Sum Root to Leaf Numbers(https://leetcode.com/problems/sum-root-to-leaf-numbers/description/)

class Solution {
public:
int sumNumbers(TreeNode* root) {
return helper(root, );
}
int helper(TreeNode *root, int sum) {
if (root == NULL) return ;
if (root->left == NULL && root->right == NULL) return sum * + root->val;
else return helper(root->left, sum * + root->val ) + helper(root->right, sum * + root->val);
}
};

8.Binary Tree Right Side View(https://leetcode.com/problems/binary-tree-right-side-view/description/)

class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode * temp = q.front();
q.pop();
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
if (i == size - ) {
res.push_back(temp->val);
}
}
}
return res;
}
};

9.Maximum Depth of Binary Tree(https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)

递归解法:

class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return ;
if (root->left == NULL && root->right == NULL) return ;
int maxl = maxDepth(root->left);
int maxr = maxDepth(root->right);
return maxl > maxr ? maxl + : maxr + ;
}
};

BFS解法:

class Solution {
public:
int maxDepth(TreeNode* root) {
int res = ;
if (root == NULL) return ;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode* temp = q.front();
q.pop();
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
}
res++;
}
return res;
}
};

10.Binary Tree Inorder Traversal(https://leetcode.com/problems/binary-tree-inorder-traversal/description/)

普通的中序遍历。

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

11.Validate Binary Search(https://leetcode.com/problems/validate-binary-search-tree/)

判断一棵二叉树是否二叉搜索树。

class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
vector<int> seq;
inOrder(seq, root);
for (int i = ; i < seq.size() - ; i++) {
if (seq[i] >= seq[i + ]) return false;
}
return true;
}
void inOrder(vector<int> &seq, TreeNode *root) {
if (root == NULL) return;
else {
inOrder(seq, root->left);
seq.push_back(root->val);
inOrder(seq, root->right);
}
}
};

12.Convert Sorted Array to Binary Search Tree(https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/)

使用分治法。

class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return BSTNode(nums, , nums.size() - );
}
TreeNode* BSTNode(vector<int> &nums, int first, int last) {
if (first > last) return NULL;
else {
int mid = (first + last) / ;
TreeNode *root = new TreeNode(nums[mid]);
root->left = BSTNode(nums, first, mid - );
root->right = BSTNode(nums, mid + , last);
return root;
} }
};

13.Balanced Binary Tree(https://leetcode.com/problems/balanced-binary-tree/description/)

判断一棵二叉树是否平衡二叉树。

/**
* 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:
bool isBalanced(TreeNode* root) {
int depth = ;
return isBalanced(root, depth);
}
bool isBalanced(TreeNode* root, int &depth) {
if (root == NULL) {
depth = ;
return true;
}
else {
int LeftDepth;
int RightDepth;
bool isLeftBalanced = isBalanced(root->left, LeftDepth);
bool isRightBalanced = isBalanced(root->right, RightDepth);
if (isLeftBalanced && isRightBalanced) {
if (abs(LeftDepth - RightDepth) <= ) {
depth = LeftDepth > RightDepth ? LeftDepth + : RightDepth + ;
return true;
} }
return false;
}
}
};

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/142096.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,070
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,316
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,310
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,910
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,098
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站