leetcode-二叉树题型

找完全二叉树最底层最右边的结点

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最右边 节点的值。
假设二叉树中至少有一个节点。

完全二叉树的特点,即除了最后一层外,每一层都是满的,并且最后一层上的节点都集中在该层最左边的若干位置上。所以,如果我们按照层次遍历这个完全二叉树,最后遍历到的节点即为底层最右节点。

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
46
47
#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 求完全二叉树的底层最右节点
TreeNode* findBottomRightNode(TreeNode* root) {
if (!root) return NULL;

queue<TreeNode*> q;
q.push(root);

TreeNode* cur = NULL;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
cur = q.front();
q.pop();

if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}

return cur;
}

int main() {
// 手动构建一个完全二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);

TreeNode* br = findBottomRightNode(root);
cout << "底层最右节点的值为:" << br->val << endl;

return 0;
}

二叉树的最近公共祖先

根据以上定义,若 root 是 p,q 的 最近公共祖先 ,则只可能为以下情况之一:

  1. p 和 q 在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
  2. p=root ,且 q 在 root 的左或右子树中;
  3. q=root ,且 p 在 root 的左或右子树中;
1
2
3
4
5
6
7
8
9
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 nullptr; // 1.
if(left == nullptr) return right; // 3.
if(right == nullptr) return left; // 4.
return root; // 2. if(left != null and right != null)
}

找到搜索二叉树中两个错误的节点

一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)

输入描述:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
ps:节点的编号就是该节点的值。

输出描述:
请按升序输出这两个错误节点的值。

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
#include <bits/stdc++.h> // 包含所有
using namespace std;

struct Tree{
int left, right; // 数字可以不用链表
};

vector<Tree> T;
vector<int> v1;

void BST(int r){
if(r==0)
return;
BST(T[r].left);
v1.push_back(r);
BST(T[r].right);
}

int main() {
int n, root, a, b, c;
cin >> n >> root;
T.resize(n+1);
for(int i=0;i<n;i++){ // n个节点
cin >> a >> b >> c; // a是从1开始的
T[a].left = b;
T[a].right = c;
}
BST(root);
vector<int> v2(v1);
sort(v2.begin(), v2.end());
for(int i=0,k=0;i<v2.size();i++){
if(v1[i]!=v2[i]){
k++;
if(k==1)
printf("%d ", v2[i]);
else{
printf("%d\n", v2[i]);
break;
}
}
}
return 0;
}
nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!