leedcode 树
链接
二叉树的最大深度
题目说明
求二叉树的最大深度
题目解析
使用递归求解即可
1
2
3
4
5
6
7
| int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return (left>=right?left+1:right+1);
}
|
验证二叉搜索树
题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
题目解析 方法一
递归验证即可。
或者中序遍历也可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool is_right(struct TreeNode* root,long low,long up)
{
if(root==NULL)
return true;
if(root->val<=low||root->val>=up)
return false;
return is_right(root->left,low,root->val)&&is_right(root->right,root->val,up);
}
bool isValidBST(struct TreeNode* root){
if(root==NULL)
return true;
return is_right(root,LONG_MIN,LONG_MAX);
}
|
题目解析 方法二
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int cur =INT_MIN;
bool isValidBST(struct TreeNode *root)
{
printf("%d \n",cur);
if (root)
{
if (!isValidBST(root->left))
return false;
printf("%d %d\n",cur,root->val);
if (cur >= root->val)
return false;
cur = root->val;
if (!isValidBST(root->right))
return false;
}
return true;
}
|
对称二叉树
题目描述
给定一个二叉树，检查它是否是镜像对称的。
题目解析 方法一
中序遍历的方法不可行，形状判定很复杂。
使用递归，若像棵树镜像，则一棵树的左子树必定和另一棵树的右子树镜像。递归判断即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool is_right(struct TreeNode *left, struct TreeNode *right)
{
if (!left && !right)
return true;
if (!left || !right)
return false;
return ((left->val == right->val) && is_right(left->left, right->right) && is_right(left->right, right->left));
}
bool isSymmetric(struct TreeNode *root)
{
return is_right(root, root);
}
|
题目解析 方法二
使用队列啊ing递归改为迭代
每次从队列中取出要进行比较的两个结点，不相等的直接返回，相等则按相反顺序插入四个孩子到队列。直到队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
deque<TreeNode *> q;
q.push_back(root);
q.push_back(root);
while (!q.empty())
{
TreeNode *left = q.front();
q.pop_front();
TreeNode *right = q.front();
q.pop_front();
if (!left && !right)
continue;
if (!left || !right)
return false;
if (left->val != right->val)
return false;
q.push_back(left->left);
q.push_back(right->right);
q.push_back(left->right);
q.push_back(right->left);
}
return true;
}
};
|
二叉树的层序遍历
题目描述
层序遍历二叉树
题目解析 方法一
根结点入队。key_num记录每一层的个数，出队一个存入数组，入队其孩子。更新key_num。直到队空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode *root)
{
vector<vector<int>> v;
deque<TreeNode *> q;
int key_num = 0;
int temp_key_num = 0;
if (!root)
return v;
q.push_back(root);
key_num++;
while (!q.empty())
{
vector<int> v1;
TreeNode *t;
while (key_num >= 1)
{
t = q.front();
v1.push_back(t->val);
q.pop_front();
key_num--;
if (t->left)
{
q.push_back(t->left);
temp_key_num++;
}
if (t->right)
{
q.push_back(t->right);
temp_key_num++;
}
}
key_num = temp_key_num;
temp_key_num = 0;
v.push_back(v1);
}
return v;
}
};
|
将有序数组转换为二叉搜索树
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
题目解析 方法一
AVL树插入的时候可能涉及不平衡需要进行旋转，但是现在是从一个确定的数组中插入，故不需要进行旋转，只需要判断插入的顺序即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution
{
public:
TreeNode *sortedArrayToBST(vector<int> &nums)
{
TreeNode *root = new TreeNode();
root->val=nums.at(nums.size() / 2);
root->left = insert(nums, 0, nums.size() / 2, root);
root->right = insert(nums, nums.size() / 2 + 1, nums.size(), root);
return root;
}
TreeNode *insert(vector<int> &nums, int low, int up, TreeNode *pa)
{
if (low != up)
{
TreeNode *t = new TreeNode();
t->val=nums.at((low + up) / 2);
t->left = insert(nums, low, (low + up) / 2, t);
t->right = insert(nums, (low + up) / 2 + 1, up, t);
return t;
}
return NULL;
}
};
|
