二叉树题目
2018-05-22 本文已影响0人
_Monk
1. 路径之和
题目
给定一个二叉树root和整数sum，找出所有从根节点到叶节点的路径，这些路径上的节点值累加和为sum
思路
对一颗二叉树，怎么找出从根节点到所有叶节点的路径？
对路径上的每个节点求和与给定的值比较
代码实现
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int value)
{
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
class Solution {
private:
void preOrder(TreeNode *root, std::vector<int> &s, int target, int &sum, std::vector<std::vector<int>> &res)
{
if (root == NULL) {
return;
}
sum += root->value; // 遍历一个节点更新一个路径值
s.push_back(root->value);
if (root->left == NULL && root->right == NULL && sum == target) { // 当到达叶节点并且路径中的节点值之和与给定的值相等, 将路径添加到结果
res.push_back(s);
}
preOrder(root->left, s, target, sum, res);
preOrder(root->right, s, target, sum, res);
sum -= root->value;
s.pop_back();
}
public:
std::vector<std::vector<int>> pathSum(TreeNode *root, int target)
{
std::vector<int> s; // 定义一个栈，用来存放路径
std::vector<std::vector<int>> res; // 定义结果的变量
int sum = 0; // 定义一个变量，用来统计栈中的元素的和是否与目标值相等
preOrder(root, s, target, sum, res);
return res;
}
};
int main()
{
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
a.right = &c;
b.left = &d;
c.left = &e;
c.right = &f;
d.left = &g;
d.right = &h;
f.left = &i;
f.right = &j;
Solution solve;
std::vector<std::vector<int>> result = solve.pathSum(&a, 22);
for (auto i : result) {
for (auto j : i) {
std::cout << j << "\t";
}
std::cout << std::endl;
}
}
2. 最近公共祖先
题目
已知一颗二叉树，求二叉树中给定的两个节点的最近公共祖先。
思路
（1）两个节点的公共祖先，肯定在从根节点到这两个节点的路径上
（2）怎么确定从根节点到这两个节点的路径
（3）从两个路径中找相同值，最后一个相等的值即为公共祖先
代码实现
#include <iostream>
#include <vector>
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int value)
{
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
class Solution {
private:
void preOrder(TreeNode *root, TreeNode *target, std::vector<TreeNode *> &path, std::vector<TreeNode *> &result,
int &finish)
{
if (root == NULL || finish == 1)
return;
path.push_back(root); // 先序遍历节点入栈
if (root == target) { // 找到目标节点
finish = 1;
result = path;
}
preOrder(root->left, target, path, result, finish);
preOrder(root->right, target, path, result, finish);
path.pop_back();
}
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
std::vector<TreeNode *> p_path; // 寻找从根节点到p节点的路径
std::vector<TreeNode *> q_path; // 寻找从根节点到q节点的路径
std::vector<TreeNode *> result1;
std::vector<TreeNode *> result2;
int finish = 0;
preOrder(root, p, p_path, result1, finish); // p节点的路径
for (auto path : result1) {
std::cout << path->value << "\t";
}
finish = 0;
std::cout << std::endl;
preOrder(root, q, q_path, result2, finish); // q节点的路径
for (auto path : result2) {
std::cout << path->value << "\t";
}
std::cout << std::endl;
// 两个路径上最后一个相同的点即为最近公共祖先
int min = result1.size() < result2.size() ? result1.size() : result2.size();
TreeNode* res = 0;
for (int i = 0; i < min; i++) {
if (result1[i] == result2[i]) {
res = result1[i];
}
}
return res;
}
};
int main()
{
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
a.right = &c;
b.left = &d;
c.left = &e;
c.right = &f;
d.left = &g;
d.right = &h;
f.left = &i;
f.right = &j;
Solution solve;
TreeNode *res = solve.lowestCommonAncestor(&a, &e, &j);
std::cout << res->value << std::endl;
}
3. 二叉树转链表
题目
给定一颗二叉树，将该二叉树就地转为单链表，单链表中节点顺序为前序遍历的顺序。
思路
对于二叉树的遍历问题，考虑遍历到每一个节点的时候需要对该节点做什么操作。
图1. 思路
代码实现
#include <iostream>
#include <vector>
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int value)
{
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
class Solution {
private:
void preOrder(TreeNode *root, TreeNode *&last)
{
if (!root) {
return;
}
if (!root->left && !root->right) {
last = root;
return;
}
// 备份左右指针
TreeNode *left = root->left;
TreeNode *right = root->right;
// 定义左右子树最后一个节点变量
TreeNode *left_last = NULL;
TreeNode *right_last = NULL;
if (left) { // 如果有左子树
preOrder(left, left_last);
root->left = NULL;
root->right = left;
last = left_last;
}
if (right) { // 如果有右子树
preOrder(right, right_last);
if (left_last) {
left_last->right = right;
}
last = right_last;
}
}
public:
void flatten(TreeNode *root)
{
TreeNode *last = NULL;
preOrder(root, last);
}
};
int main()
{
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
TreeNode d(4);
TreeNode e(5);
TreeNode f(6);
a.left = &b;
a.right = &e;
b.left = &c;
b.right = &d;
e.right = &f;
Solution solve;
solve.flatten(&a);
TreeNode *root = &a;
while (root) {
if (root->left) {
std::cout << "error" << std::endl;
}
std::cout << root->value << "\t";
root = root->right;
}
}
4. 侧面观察二叉树
题目
给定一个二叉树，假设从二叉树的右侧观察它，将观察到的节点按照从上到下的顺序输出
思路
该问题就是二叉树按层遍历，可以观测到的节点就是每一层最右侧的节点。
代码
#include <iostream>
#include <queue>
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int value)
{
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
class Solution {
public:
std::vector<int> rightsideview(TreeNode *root)
{
std::queue<std::pair<TreeNode*, int>> Q;
std::vector<int> view;
if (root) {
Q.push(std::make_pair(root, 0));
}
while (!Q.empty()) {
TreeNode* node = Q.front().first; // 当前访问的节点
int depth = Q.front().second; // 当前访问的节点的层数
Q.pop();
if (view.size() == depth) {
view.push_back(node->value);
}
else {
view[depth] = node->value;
}
if (node->left) {
Q.push(std::make_pair(node->left, depth+1));
}
if (node->right) {
Q.push(std::make_pair(node->right, depth+1));
}
}
return view;
}
};
int main()
{
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
TreeNode d(4);
TreeNode e(5);
TreeNode f(6);
a.left = &b;
a.right = &c;
b.right = &e;
c.right = &d;
e.left = &f;
Solution solve;
std::vector<int> res;
res = solve.rightsideview(&a);
for (auto i : res) {
std::cout << i << std::endl;
}
}
