找完全二叉树最底层最右边的结点
给定一个二叉树的 根节点 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 的 最近公共祖先 ,则只可能为以下情况之一:
- p 和 q 在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
- p=root ,且 q 在 root 的左或右子树中;
- 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; if(left == nullptr) return right; if(right == nullptr) return left; return root; }
|
找到搜索二叉树中两个错误的节点
一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
输入描述:
第一行输入两个整数 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++){ cin >> a >> b >> c; 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; }
|