Java教程
编程题分类——树
本文主要是介绍编程题分类——树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
前言
技巧
- 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。
正文
1. 按之字形顺序打印二叉树
code
答案
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* root) {
vector<vector<int>> arr_out;
vector<int> arr_small;
if(root==nullptr)
return arr_out;
stack<TreeNode*> st1;
stack<TreeNode*> st2;
st1.push(root);
while(!st1.empty()||!st2.empty())
{
while(!st1.empty())
{
TreeNode* temp1 = st1.top();
arr_small.push_back(temp1->val);
if(temp1->left)
st2.push(temp1->left);
if(temp1->right)
st2.push(temp1->right);
st1.pop();
}
if(arr_small.size())
{
arr_out.push_back(arr_small);
arr_small.clear();
}
while(!st2.empty())
{
TreeNode* temp2 = st2.top();
arr_small.push_back(temp2->val);
if(temp2->right)
st1.push(temp2->right);
if(temp2->left)
st1.push(temp2->left);
st2.pop();
}
if(arr_small.size())
{
arr_out.push_back(arr_small);
arr_small.clear();
}
}
return arr_out;
}
};
2. 层序遍历二叉树
反正就是用队列。
code
答案
void layerTrace(BTreeNode *T)
{
if(T== nullptr)//先判断这棵树是否为空
return;
BTreeNode *p=T;
queue<BTreeNode*>q;
q.push(p);//然后让头结点先入队列
while(!q.empty())//这里可以去判断队列是否非空
{
p=q.front();//队列中的元素出来，
q.pop();
cout<<<<p->data;
if(p->left!= nullptr)q.push(p->left);//找左子树，让其入队列
if(p->right!= nullptr)q.push(p->right);//找，让其入队列右子树
}
}
3. 完全二叉树怎么判断？
思路:转变思路，如何判断该树不是完全二叉树，就是层序遍历已经输出null节点了，后面却还有节点。
完全二叉树的性质:从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶结点都向左边靠拢填满。
code
答案
class Solution
{
public:
bool isCompleteTree(TreeNode* root)
{
queue<TreeNode*> q;
bool reachNull = false;
q.push(root);
while (!q.empty())
{
TreeNode* cur = q.front();
q.pop();
if (cur == nullptr)
{
reachNull = true;
continue;
}
else
{
if (reachNull)
{
return false;
}
q.push(cur->left);
q.push(cur->right);
}
}
return true;
}
};
3、 二叉树的序列化和反序列化
4. 二叉搜索树的第k个结点
题目
方法一:
code
答案
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* res;
TreeNode* KthNode(TreeNode* root, int k) {
inOrder(root,k);
return res;
}
void inOrder(TreeNode* root,int& k)
{
//中序遍历，第k个节点即为所求的节点
if(root==nullptr)
return;
if(root->left)
inOrder(root->left,k);
k--;//error1:要先进行减法
if(k==0)
res = root;
if(root->right)
inOrder(root->right,k);
}
};
方法二：非递归的方式，维护一个栈。
答案
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* root, int k) {
//中序遍历，非递归的话，需要维护一个栈
stack<TreeNode*> st;
TreeNode* res = NULL;//error3：要最终返回的元素，一般要记得进行初始化
int n = 0;
TreeNode* cur = root;
while(!st.empty()||cur)
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
cur= st.top();//error1:注意当前栈顶元素要赋给cur
n++;
st.pop();
if(n==k)
{
res = cur;
return res;
}
cur = cur->right;//error2:直接把当前元素的右节点也放入栈即可
}
return res;
}
};
5. 重建二叉树
题目
code
答案
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size()==0||vin.size()==0)
return nullptr;
int rootVal = pre[0];
int rootIndex = 0;
TreeNode* root = new TreeNode(rootVal);
for(int i = 0;i<vin.size();i++)
{
if(vin[i]==rootVal)
{
rootIndex = i;
break;
}
}
vector<int> pre_left;
vector<int> vin_left;
vector<int> pre_right;
vector<int> vin_right;
for(int j = 0;j<rootIndex;j++)
{
pre_left.push_back(pre[j+1]);
vin_left.push_back(vin[j]);
}
for(int k = rootIndex+1;k<vin.size();k++)
{
pre_right.push_back(pre[k]);
vin_right.push_back(vin[k]);
}
root->left = reConstructBinaryTree(pre_left,vin_left);
root->right = reConstructBinaryTree(pre_right,vin_right);
return root;
}
};
6. 树的子结构
题目
code
答案
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr||root2==nullptr)
return false;
bool result;
if(root1->val==root2->val)//如果当前的节点是相等的，就继续递归比较其他节点
{
result = Hastree(root1,root2);
}
if(!result)
{
result = HasSubtree(root1->left,root2); //否则就拿左节点和子结构进行比较
}
if(!result)
{
result = HasSubtree(root1->right,root2);//否则就拿右节点和子结构进行比较
}
return result;
}
bool Hastree(TreeNode* root1,TreeNode* root2)
{
if(root2==NULL)
return true;
if(root1==NULL)
return false;
if(root1->val!=root2->val)
return false;
return Hastree(root1->left,root2->left)&&Hastree(root1->right,root2->right);
}
};
7. 二叉树的镜像
题目
code
答案
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
TreeNode* Mirror(TreeNode* root) {
//类似于后序遍历
if(root==nullptr)
return nullptr;
Mirror(root->left);
Mirror(root->right);
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
return root;
}
};
8. 二叉树的最近公共祖先
题目
9. 二叉树的遍历(前序，中序，后序，递归+迭代 )
9_1_1. 前序遍历（递归）
code
答案
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL)
return;
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
9_1_2.前序遍历(迭代）
code
答案
vector<int> preorder(TreeNode* root)
{
vector<int> res;
if(root==NULL)
return res;
stack<TreeNode*> st;
st.push(root);
while(!st.empty())
{
TreeNode* node = st.top();
res.push(node);
st.pop();
if(node->right)
st.push(node->right);
if(node->left)
st.push(node.left);
}
return result;
}
10. 二叉树的最近公共祖先
题目
code
答案
/**
* 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||root==p||root==q)
return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left!=nullptr&&right!=nullptr)
return root;
else if(left!=nullptr)
return left;
else if(right!=nullptr)
return right;
return nullptr;
}
};
这道题目应该就是普通的递归，其实跟回溯应该没什么关系了，可能一讲到二叉树，大部分的思路应该都要是递归的思路会比较对。
11. 二叉搜索树中的插入操作
题目
解题思路
此题的解题核心，还是说要找到合适的位置，去插入这个节点。
那么插入有两种方式，
第一：按照普通的插入方式，让parent节点指向当前要插入的这个位置。我当时也是觉得这个位置很难找。
第二：采用递归的方式，找到合适的位置，返回这个插入的节点就可以了。
代码
方法一
答案
/**
* 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* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr)
{
root = new TreeNode(val);
return root;
}
if(val>root->val)
{
root->right = insertIntoBST(root->right,val);
}
else
{
root->left = insertIntoBST(root->left,val);
}
return root;
}
};
方法二
code
答案
/**
* 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* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr)
{
root = new TreeNode(val);
return root;
}
TreeNode* parent = nullptr;
bst(root,val,parent);
return root;
}
void bst(TreeNode* cur,int val,TreeNode* parent)
{
if(cur==nullptr)
{
TreeNode* node = new TreeNode(val);
if(val>parent->val)
parent->right = node;
else
parent->left = node;
return;
}
parent = cur;
if(parent->val>val)
bst(cur->left,val,parent);
else
bst(cur->right,val,parent);
}
};
12. 二叉树的最大深度
二叉树的最大深度
方法一：递归
code
答案
/**
* 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;
int left = maxDepth(root->left);//计算左节点
int right = maxDepth(root->right);//计算右子树
return max(left,right)+1;
}
};
方法二:迭代
code
答案
/**
* 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) {
//13:52->
//弄一个队列来保存这些数值
if(root==nullptr)
return 0;
queue<TreeNode*> q;
q.push(root);
int count=0;
while(!q.empty())
{
int size = q.size();
for(int i = 0;i<size;i++)
{
TreeNode* node = q.front();//取出元素
q.pop();
if(node->left)//加入其孩子节点
q.push(node->left);
if(node->right)
q.push(node->right);
}
count++;
}
return count;
}
};
方法三：前序遍历 回溯——从上往下找
code
答案
/**
* 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 result = 0;
int maxDepth(TreeNode* root) {
if(root==nullptr)
return 0;
getDepth(root,1);
return result;
}
void getDepth(TreeNode* node,int depth)
{
if(result<depth)
result = depth;
if(node->left==nullptr&&node->right==nullptr)
return;
if(node->left)
{
depth++;
getDepth(node->left,depth);
depth--;
}
if(node->right)
{
depth++;
getDepth(node->right,depth);
depth--;
}
return;
}
};
13. 左叶子之和
题目
方法1:迭代 code
答案
/**
* 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 sumOfLeftLeaves(TreeNode* root) {
//递归不会用迭代的方式
if(root==nullptr)
return 0;
queue<TreeNode*> q;
q.push(root);
int sum = 0;
while(!q.empty())
{
int size = q.size();
for(int i = 0;i<size;i++)
{
TreeNode* node = q.front();
if(node->left)
{
if(node->left->left==nullptr&&node->left->right==nullptr)//error1：疏忽了左叶子节点的定义
sum+=node->left->val;
q.push(node->left);
}
if(node->right)
{
q.push(node->right);
}
q.pop();
}
}
return sum;
}
};
方法二：递归法
code
答案
/**
* 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 sum = 0;
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr)
return 0;
int left = sumOfLeftLeaves(root->left);
int right = sumOfLeftLeaves(root->right);
if(root->left)
{
if(root->left->left==nullptr&&root->left->right==nullptr)
sum+=root->left->val;
}
return sum;
}
};
参考
- 剑指Offer
- Leetcode 100题
这篇关于编程题分类——树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
后台交互资料入门指南11-14
-
如何轻松创建项目环境：新手入门教程11-14
-
如何抽离公共代码：初级开发者指南11-14
-
Python编程入门指南11-14
-
Python编程入门：如何获取参数11-14
-
JWT 用户校验：简单教程与实践11-14
-
Pre-commit 自动化测试入门指南11-14
-
Python编程基础11-14
-
Server Action入门教程：轻松掌握服务器操作11-14
-
Server Component入门教程：轻松搭建服务器组件11-14
-
用useRequest实现数据请求的简单教程11-14
-
RestfulAPI课程：初学者的全面指南11-14
-
Server Action课程：入门级教程11-14
-
Server Component课程入门指南11-14
-
dnd-kit学习：初学者指南11-14
栏目导航
