二叉树三种遍历
递归
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//构造二叉树
TreeNode* CreatTree(vector<int>& num) {
int length = num.size();
//如果传入容器为空，则跳出函数，无法构建二叉树
if (length == 0) return nullptr;
//赋值的索引位置
int index = 0;
//构建一个二叉树
TreeNode *root = new TreeNode(num[index++]);
//构建二叉树时所用的工具
TreeNode *p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
//当队列不为空，此时还有数字没插入树中
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && num[index] != -1) {
TreeNode *LeftNode = new TreeNode(num[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length&&num[index] != -1) {
TreeNode *RightNode = new TreeNode(num[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
//前序遍历 根左右
void Preorder(TreeNode *root)
{
//根为空，则跳出函数
if (!root)
return;
//输出根的值
cout << root->val << " ";
//递归获取左子树的值
Preorder(root->left);
//递归获取右子树的值
Preorder(root->right);
}
//中序遍历 左根右
void Midorder(TreeNode *root)
{
//根为空，则跳出函数
if (!root)
return;
//递归获取左子树的值
Midorder(root->left);
cout << root->val << " ";
Midorder(root->right);
}
//后序遍历 左右根
void Postorder(TreeNode *root)
{
if (!root)
return;
Postorder(root->right);
Postorder(root->left);
cout << root->val << " ";
}
int main()
{
vector<int> num = { 3,5,1,6,2,0,8,-1,-1,7,4,-1,-1,-1,-1 };
TreeNode *tree = CreatTree(num);
//前序遍历
Preorder(tree);
//中序遍历
Midorder(tree);
//后序遍历
Postorder(tree);
return 0;
}
Leetcode 113
题意：每层取一个节点，各节点之间为父子关系。判断是否存在总和等于给定数值sum的路径。
考点：深度优先搜索
// 知识点：创建二叉树；深度遍历
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//定义二叉树
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
//构造函数，初始数据依次为价值，左子节点，右子节点
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
//二维数组，存储所有满足sum的路径
vector<vector<int>> pathSum(TreeNode* root, int sum) {
//存储所有满足条件的路径
vector<vector<int>> paths;
//存储当前遍历路径
vector<int> temp;
help(root, paths, temp, sum);
//返回二维数组
return paths;
}
//TreeNode* &root vector<int> temp 这块没用引用，是每条路径都是相互独立的
//vector<vector<int>> &paths用引用是因为自始至终他就一个
void help(TreeNode* &root, vector<vector<int>> &paths, vector<int> temp, int sum) {
if (root == nullptr)
//结束函数
return;
//将根节点的值传入temp中
temp.push_back(root->val);
if (root->left == nullptr && root->right == nullptr && sum == root->val)
//将符合要求的容器压入path中
paths.push_back(temp);
if (root->left != nullptr)
//递归 用sum - root->val因为sum要抛去该容器内加入了的元素的值
help(root->left, paths, temp, sum - root->val);
if (root->right != nullptr)
//递归 不断深入，到两侧子节点都为空的时候，该点是叶子结点，就是该路径的尽头了
help(root->right, paths, temp, sum - root->val);
}
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num) {
//树中总节点个数
int len = num.size();
if (len == 0) {
return nullptr;
}
queue<TreeNode*> queue;
int index = 0;
// 创建根节点，这里调用了[]的重载函数
//将整棵树存在这里
TreeNode *root = new TreeNode(num[index]);
index++;
// 入队列，队列在这里就是一个传递的容器，每次循环会排空上次存的值并存入上次存的值的两个子节点
queue.push(root);
//空对象，该对象只有一个val，两个指针和一个成员函数
TreeNode *p = nullptr;
//如果queue为空，则证明上一次循环并没有压入任何左子节点或右子节点，证明上一次循环中的root是叶子结点
while (!queue.empty() && index < len) {
// 第一次进来的时候，存入了*root的那个根节点
//出队列，存储上次循环中的root节点，并将之前存入的值清空
p = queue.front();
queue.pop();
// 左节点
if (index < len && num[index] != -1) {
// （-1代表该节点为空）如果不空创建一个节点，存入num中的值作为左子节点
TreeNode *leftNode = new TreeNode(num[index]);
//压入获取的num里的值到root里面，作为左子节点
p->left = leftNode;
queue.push(leftNode);
}
index++;
// 右节点
if (index < len && num[index] != -1) {
// 如果不空创建一个节点，存入num中的值作为右子节点
TreeNode *rightNode = new TreeNode(num[index]);
//压入获取的num里的值root里面，作为右子节点
p->right = rightNode;
queue.push(rightNode);
}
index++;
}
return root;
}
int main()
{
//创建解决问题的类的对象
Solution s;
// -1代表该节点为空 按层传入 根：5 第二层：4,8 第三层：11，-1,13,4 以此类推
vector<int> num = { 5,4,8,11,-1,13,4,7,2,-1,-1,5,1 };
//创建二叉树
TreeNode* root = CreateTreeByLevel(num);
//输出二叉树中符合要求的路径
vector<vector<int> > paths = s.pathSum(root, 22);
//遍历输出结果，每输出完二维数组的一行就输出一个换行符
for (int i = 0; i < paths.size(); i++) {
for (int j = 0; j < paths[i].size(); j++) {
cout << paths[i][j] << " ";
}
cout << endl;
}
return 0;
}
Leetcode 236
题意：找到给定的两个节点最近的公共祖先。
思路：1、如果一个节点是另一个节点的祖先，则最近的公共祖先就是两个节点中作为祖先的那一个。
2、如果root的左子树p和右子树q都存在，则root肯定是最近祖先。
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//构造二叉树
TreeNode* CreatTree(vector<int>& num) {
int length = num.size();
//如果传入容器为空，则跳出函数，无法构建二叉树
if (length == 0) return nullptr;
//赋值的索引位置
int index = 0;
//构建一个二叉树
TreeNode *root = new TreeNode(num[index++]);
//构建二叉树时所用的工具
TreeNode *p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
//当队列不为空，此时还有数字没插入树中
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && num[index] != -1) {
TreeNode *LeftNode = new TreeNode(num[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length&&num[index] != -1) {
TreeNode *RightNode = new TreeNode(num[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
//递归找到结果
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
//如果pq都在root的左子树，那么就需要递归root的左子树，右子树同理
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//如果root的左子树存在p，右子树存在q，那么root肯定就是最近祖先
if (left && right) {
return root;
}else {
return left == nullptr ? right : left;
}
}
int main()
{
vector<int> num = { 3,5,1,6,2,0,8,-1,-1,7,4,-1,-1,-1,-1 };
int first_num = 0, second_num = 0;
cin >> first_num;
cin >> second_num;
TreeNode *tree = CreatTree(num);
//不会调用这个函数。。。卡住了。。。。。。。。。。
lowestCommonAncestor(root, first_num, second_num);
return 0;
}
leetcode 114
题意：二叉树按前序遍历生成一棵没有左子树的二叉树。
考点：二叉树前序遍历
思路：还是要用递归了。
//前序遍历树，把值压入链表
#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//构造二叉树
TreeNode* CreatTree(vector<int> num) {
int length = num.size();
//如果传入容器为空，则跳出函数，无法构建二叉树
if (length == 0) return nullptr;
//赋值的索引位置
int index = 0;
//构建一个二叉树
TreeNode *root = new TreeNode(num[index++]);
//构建二叉树时所用的工具
TreeNode *p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
//当队列不为空，此时还有数字没插入树中
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && num[index] != -1) {
TreeNode *LeftNode = new TreeNode(num[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length&&num[index] != -1) {
TreeNode *RightNode = new TreeNode(num[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
TreeNode* Preorder(TreeNode *root)
{
queue<TreeNode *>s;
//根为空，则跳出函数
if (!root)
return;
helper(s, root);
TreeNode *head = root;
s.pop();
//将会去的内容依次放入新的树中
while (s.size() > 0) {
head->right = s.front();
head->left = nullptr;
head = head->right;
s.pop();
}
return head;
}
//前序遍历思想
void helper(std::queue<TreeNode*>& s, TreeNode* root) {
if (root == nullptr) {
return;
}
s.push(root);
helper(s, root->left);
helper(s, root->right);
}
int main()
{
vector<int> num = { 1,2,5,3,4,-1,6 };
TreeNode *tree = CreatTree(num);
TreeNode * answer=Preorder(tree);
return 0;
}
找到一个别的解题思路，没看懂，先记录一下
原文链接：http://blog.csdn.net/zjajgyy/article/details/77478333
class Solution {
public:
void flatten(TreeNode *root) {
TreeNode*now = root;
while (now)
{
if(now->left)
{
//Find current node's prenode that links to current node's right subtree
TreeNode* pre = now->left;
while(pre->right)
{
pre = pre->right;
}
pre->right = now->right;
//Use current node's left subtree to replace its right subtree(original right
//subtree is already linked by current node's prenode
now->right = now->left;
now->left = NULL;
}
now = now->right;
}
}
};LeetCode 199
题意：依次输出按层遍历最右侧的子节点的值。
考点：层序遍历，深度优先搜索
思路：层序遍历：每层最后入队的那个值就是要输出的值； 深度优先遍历：反向遍历，右子树优先搜索（这个方法感觉效率不高）。
层序遍历的主要思路就是先把根节点存入，然后输出，输出的同时把根节点的左右孩子存入，再把左孩子输出，同样输出的同时把左孩子的孩子在存入，直到遍历完成，例如：
a
b c
d e f g
先把a存入，然后输出a，输出a的同时把b c存入，然后再输出b,输出b的同时存入d e，继续输出c，然后存入f g，直到全部输出
二叉树层序遍历代码如下(学习了一种新的二叉树的赋值方法)：
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void answer(TreeNode* arr[])
{
queue<TreeNode*> rel; //定义一个队列，数据类型是二叉树指针，不要仅是int！！不然无法遍历
rel.push(arr[0]);
while (!rel.empty())
{
TreeNode* front = rel.front();
cout << front->val << endl;
//删除最前面的节点
rel.pop();
//判断最前面的左节点是否为空，不是则放入队列
if (front->left != nullptr)
rel.push(front->left);
//判断最前面的右节点是否为空，不是则放入队列
if (front->right != nullptr)
rel.push(front->right);
}
}
int main()
{
//构建二叉树
TreeNode* s_arr[6];
s_arr[0] = new TreeNode(0);
s_arr[1] = new TreeNode(1);
s_arr[2] = new TreeNode(2);
s_arr[3] = new TreeNode(3);
s_arr[4] = new TreeNode(4);
s_arr[5] = new TreeNode(5);
s_arr[0]->left = s_arr[1]; // 0
s_arr[0]->right = s_arr[2]; // 1 2
s_arr[1]->left = s_arr[3]; // 3 5
s_arr[3]->left = s_arr[4]; //4
s_arr[2]->right = s_arr[5]; //所以层序遍历的结果为：0 1 2 3 5 4
answer(s_arr);
return 0;
}广度优先解法
自己写了一个按层遍历的，似乎不太完美。
/*
deque的一些操作
c.size(); //返回当前的元素数量
c.empty(); //判断大小是否为零。等同于c.size() == 0,但可能更快
c.max_size(); //可容纳元素的最大数量
c.at(idx) ; //返回索引为idx所标示的元素。如果idx越界，抛出out_of_range
c[idx] ; //返回索引idx所标示的元素。不进行范围检查
c.front() ; //返回第一个元素,不检查元素是否存在
c.back(); //返回最后一个元素
c.begin(); //返回一个随机迭代器，指向第一个元素
c.end(); //返回一个随机迭代器，指向最后元素的下一位置
*/
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<math.h>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
vector<int> answer(TreeNode* arr[])
{
//定义一个队列，数据类型是二叉树指针，不要仅是int,不然无法遍历
queue<TreeNode*> rel;
deque<TreeNode*> answer1;
vector<int> answer2;
rel.push(arr[0]);
while (!rel.empty())
{
TreeNode* front = rel.front();
//cout << front->val << endl;
answer1.push_back(rel.front());
//删除最前面的节点
rel.pop();
//判断最前面的左节点是否为空，不是则放入队列
if (front->left != nullptr)
rel.push(front->left);
//判断最前面的右节点是否为空，不是则放入队列
if (front->right != nullptr)
rel.push(front->right);
}
//answer1.size()返回值类型是size_t
int flag = answer1.size();
int ceng = 0;
while (flag) {
if (flag / 2 >= 2) {
ceng++;
flag = flag / 2;
}
else {
break;
}
}
//树有这些层
ceng += 2;
for (int i = answer1.size()-1; i >0;) {
if (ceng > 0) {
if (answer1[i]->val != -1 && pow(2, ceng)-2 >= i && pow(2, ceng-1)-1 <= i) {
answer2.push_back(answer1[i]->val);
i = pow(2, ceng-1)-2;
ceng--;
}
else {
i--;
}
}
else {
break;
}
}
answer2.push_back(answer1[0]->val);
return answer2;
}
int main()
{
//构建二叉树
TreeNode* s_arr[7];
s_arr[0] = new TreeNode(1);
s_arr[1] = new TreeNode(2);
s_arr[2] = new TreeNode(3);
s_arr[3] = new TreeNode(-1);
s_arr[4] = new TreeNode(5);
s_arr[5] = new TreeNode(-1);
s_arr[6] = new TreeNode(4);
s_arr[0]->left = s_arr[1]; // 1
s_arr[0]->right = s_arr[2]; // 2 3
s_arr[1]->left = s_arr[3]; // -1 5 -1 4
s_arr[1]->right = s_arr[4];
s_arr[2]->left = s_arr[5];
s_arr[2]->right = s_arr[6];
answer(s_arr);
return 0;
}
网上收集了一个广度优先的解法，很不错
http://blog.csdn.net/liuchuo/article/details/51990665
/*
deque的一些操作
c.size(); //返回当前的元素数量
c.empty(); //判断大小是否为零。等同于c.size() == 0,但可能更快
c.max_size(); //可容纳元素的最大数量
c.at(idx) ; //返回索引为idx所标示的元素。如果idx越界，抛出out_of_range
c[idx] ; //返回索引idx所标示的元素。不进行范围检查
c.front() ; //返回第一个元素,不检查元素是否存在
c.back(); //返回最后一个元素
c.begin(); //返回一个随机迭代器，指向第一个元素
c.end(); //返回一个随机迭代器，指向最后元素的下一位置
*/
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<math.h>
using namespace std;
//定义树的基本框架
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//构造二叉树
TreeNode* CreatTree(vector<int> num) {
int length = num.size();
//如果传入容器为空，则跳出函数，无法构建二叉树
if (length == 0) return nullptr;
//赋值的索引位置
int index = 0;
//构建一个二叉树
TreeNode *root = new TreeNode(num[index++]);
//构建二叉树时所用的工具
TreeNode *p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
//当队列不为空，此时还有数字没插入树中
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && num[index] != -1) {
TreeNode *LeftNode = new TreeNode(num[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length&&num[index] != -1) {
TreeNode *RightNode = new TreeNode(num[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
//按层遍历
vector<int> rightSideView(TreeNode* root) {
vector<int> v;
queue<TreeNode*> q;
if (root == NULL)
return v;
q.push(root);
TreeNode* h=nullptr;
while (!q.empty()) {
//整棵树压入时，size值为1，将根的两个子树压入之后，size值为2
int size = q.size();
while (size--) {
h = q.front();
q.pop();
//子树非空，则压入队列
if (h->left != NULL)
q.push(h->left);
if (h->right != NULL)
q.push(h->right);
}
v.push_back(h->val);
}
return v;
}
int main()
{
vector<int> num = { 1,2,3,-1,5,-1,4 };
TreeNode *tree = CreatTree(num);
vector<int> answer=rightSideView(tree);
return 0;
}
深度优先的解法
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode * right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){ }
};
//构造二叉树
TreeNode* CreatTree(vector<int>num)
{
int len = num.size();
if (len == 0) return nullptr;
int index = 0;
TreeNode* root = new TreeNode(num[index++]);
TreeNode* p = nullptr;
queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()&&index<len) {
p=queue.front();
queue.pop();
if (index < len && num[index] != -1) {
TreeNode* LeftNode = new TreeNode(num[index]);
p = LeftNode;
queue.push(LeftNode);
}index++;
if (index < len && num[index] != -1) {
TreeNode* RightNode = new TreeNode(num[index]);
p = RightNode;
queue.push(RightNode);
}index++;
}
}
//深度优先遍历
vector<int> rightSideView(TreeNode* root) {
vector<int> rlt;
dfs(root, 1, rlt);
return rlt;
}
void dfs(TreeNode* root, int step, vector<int>& vec)
{
if (!root) return;
if (vec.size()<step) vec.push_back(root->val);
dfs(root->right, step + 1, vec);
dfs(root->left, step + 1, vec);
}
int main()
{
vector<int>num = { 1,2,3,-1,5,-1,4 };
TreeNode* answer = CreatTree(num);
rightSideView(answer);
dfs(answer, 1, num);
return 0;
}
未完待续。。。。。。。。。。。。。