二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
有两种方式实现，一种是深度优先遍历，一种是层序遍历，都可以获得最大深度：
深度优先遍历可以用递归或者非递归（自己用栈）来实现。
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
42
43
44
45
|
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL) return 0;
int l1 = maxDepth(root->left);
int l2 = maxDepth(root->right);
return max(l1, l2) + 1;
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL) return 0;
stack<pair<TreeNode*,int>> s;
TreeNode* p=root;
int Maxdeep=0;
int deep=0;
while(!s.empty()||p!=NULL)
{
while(p!=NULL)
{
s.push(pair<TreeNode*,int>(p,++deep));
p=p->left;
}
p=s.top().first;
deep=s.top().second;
if(Maxdeep<deep) Maxdeep=deep;
s.pop();
p=p->right;
}
return Maxdeep;
}
};
|
层序遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL) return 0;
deque<TreeNode*> q;
q.push_back(root);
int deep=0;
while(!q.empty())
{
deep++;
int num=q.size();
for(int i=1;i<=num;i++)
{
TreeNode* p=q.front();
q.pop_front();
if(p->left) q.push_back(p->left);
if(p->right) q.push_back(p->right);
}
}
return deep;
}
};
|
验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
1
2
3
4
5
| 输入:
2
/ \
1 3
输出: true
|
示例 2:
1
2
3
4
5
6
7
8
9
| 输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
|
中序遍历，把遍历到的值加入到一个数组中，最后再看其是否有序，这是效率较低的一种方法。
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
|
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> ts;
vector<int> vals;
TreeNode* cur = root;
if (root == NULL) return true;
while (cur != NULL || !ts.empty())
{
if (cur == NULL)
{
cur = ts.top();
ts.pop();
vals.push_back(cur->val);
cur = cur->right;
}
else
{
ts.push(cur);
cur = cur->left;
}
}
for(int i = 0; i < vals.size() - 1; ++i)
{
if(vals[i] >= vals[i + 1])
return false;
}
return true;
}
};
|
一种优化是不需要一个数组去记录，而是在遍历的过程中比较大小，看元素是否有序。
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 isValidBST(TreeNode* root) {
stack<TreeNode*> ts;
long val = LONG_MIN;
TreeNode* cur = root;
if (root == NULL) return true;
while (cur != NULL || !ts.empty())
{
if (cur == NULL)
{
cur = ts.top();
if(cur->val <= val)
{
return false;
}
val = cur->val;
ts.pop();
cur = cur->right;
}
else
{
ts.push(cur);
cur = cur->left;
}
}
return true;
}
};
|
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
2
3
4
5
| 1
/ \
2 2
/ \ / \
3 4 4 3
|
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
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
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> q1, q2;
if(root == NULL) return true;
if(root->left == NULL && root->right == NULL) return true;
if(root->left == NULL || root->right == NULL) return false;
q1.push(root->left);
q2.push(root->right);
while(!q1.empty() && !q2.empty())
{
TreeNode* node1 = q1.front();
TreeNode* node2 = q2.front();
q1.pop();
q2.pop();
if(node1 && !node2 || !node1 && node2) return false;
if(node1)
{
if(node1->val != node2->val) return false;
q1.push(node1->left);
q2.push(node2->right);
q1.push(node1->right);
q2.push(node2->left);
}
}
return true;
}
};
|
二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
层序遍历
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
|
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> tq;
vector<vector<int>> res;
if(root == NULL) return res;
tq.push(root);
while(!tq.empty())
{
int size = tq.size();
vector<int> temp;
while(size > 0)
{
temp.push_back(tq.front()->val);
if(tq.front()->left != NULL)
tq.push(tq.front()->left);
if(tq.front()->right != NULL)
tq.push(tq.front()->right);
tq.pop();
--size;
}
res.push_back(temp);
}
return res;
}
};
|
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
1
2
3
4
5
6
7
8
9
| 给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
|
用二分搜索的方式
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
|
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0) return NULL;
return getBST(nums, 0, nums.size() - 1);
}
TreeNode* getBST(vector<int>& nums, int l, int r)
{
if(l > r) return NULL;
int mid = (l + r) / 2;
TreeNode* cur = new TreeNode(nums[mid]);
cur->left = getBST(nums, l, mid - 1);
cur->right = getBST(nums, mid + 1, r);
return cur;
}
};
|
