二叉树的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
1
2
3
4
5
6
7
8
9
10
11
12
13
| TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode *l = lowestCommonAncestor(root->left, p, q);
TreeNode *r = lowestCommonAncestor(root->right, p, q);
if (l && r)
return root;
else if (l)
return l;
else
return r;
}
|
判断是否是相同的树
https://leetcode-cn.com/problems/same-tree/
1
2
3
4
5
6
7
| bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
|
判断是否是另一个树的子树
https://leetcode-cn.com/problems/subtree-of-another-tree/
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s || !t) return false;
if (isSameTree(s, t)) return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
|
判断是否对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/
1
2
3
4
5
6
7
8
9
10
11
12
| bool isSymmetric(TreeNode *root)
{
return isMirror(root, root);
}
bool isMirror(TreeNode *left, TreeNode *right)
{
if (!left && !right) return true;
if (!left || !right) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}
|
翻转二叉树
https://leetcode-cn.com/problems/invert-binary-tree/
1
2
3
4
5
6
7
8
9
10
| TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
TreeNode *left = root->left;
TreeNode *right = root->right;
root->left = right;
root->right = left;
invertTree(left);
invertTree(right);
return root;
}
|
BFS
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
BFS 时不携带层级信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vector<int> bfs(TreeNode* root) {
vector<int> ret;
if (!root) return ret;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *cur = q.front();
q.pop();
ret.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
return ret;
}
|
BFS 时携带层级信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (!root) return ret;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
vector<int> curLevel;
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode *cur = q.front();
q.pop();
curLevel.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
ret.push_back(curLevel);
}
return ret;
}
|