day14
二叉树
// 二叉树的C++定义
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL),right(NULL) {}
};
// 单链表定义
struct ListNode{
int val;
ListNode *node;
ListNode(int x):val(x),next(NULL){} //节点的构造函数
};
144.二叉树的前序遍历
题目链接：144. 二叉树的前序遍历
解题思路：递归法
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单调递归的逻辑
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// C++中二叉树的代码实现
// struct TreeNode{
// int val;
// TreeNode *left;
// TreeNode *right;
// Treenode( int x ) : val(x),left(NULL),right(NULL){}
// };
class Solution {
public:
// 前序遍历代码
void Traversal( TreeNode *cur, vector<int>& vec){
if( cur == NULL){
return ;
}
vec.push_back( cur->val ); //中
Traversal( cur->left , vec); //左
Traversal( cur->right , vec); //右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
Traversal( root , result);
return result;
}
};
//迭代法进行前序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// 定义栈存储二叉树节点
stack<TreeNode*> st;
vector<int> vec;
if ( root == NULL ) return vec;
st.push( root );
while( !st.empty()){
TreeNode* node = st.top();
st.pop();
// vec.push_back( node );
if ( node != NULL ) vec.push_back( node->val ); //中
else continue;
st.push( node -> right );//右 先放右边的，再放左边的，因为栈是先入后出。
st.push( node -> left ); //左
}
return vec;
}
};
145.二叉树的后序遍历
题目链接：145. 二叉树的后序遍历
解题思路：递归法
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单调递归的逻辑
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// C++实现二叉树
// struct TreeNode{
// int val;
// TreeNode* left;
// TreeNode* right;
// TreeNode(int x): val(x),left(NULL),right(NULL){}
// };
class Solution {
public:
// 后序遍历递归代码
void Traversal( TreeNode* cur,vector<int>& vec){
if ( cur == NULL){
return;
}
Traversal( cur->left ,vec);
Traversal( cur->right,vec);
vec.push_back( cur->val );
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
Traversal( root,result );
return result;
}
};
//迭代法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if ( root == NULL) return result;
st.push( root );
while( !st.empty()){
TreeNode* node = st.top(); //存储栈顶元素
st.pop();//弹出栈顶元素
if ( node != NULL ){ //如果node不为空，将该值加到result中 相当于中
result.push_back( node->val);
}
else continue;
st.push( node->left); //相当于左
st.push( node->right); //相当于右
}
// 参考前序遍历，反转结果 中左右->中右左->左右中 栈的不同
reverse(result.begin(),result.end());
return result;
}
};
94.二叉树的中序遍历
题目链接：94. 二叉树的中序遍历
解题思路：递归法
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单调递归的逻辑
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// C++实现二叉树
// struct TreeNode{
// int val;
// TreeNode* left;
// TreeNode* right;
// TreeNode( int x):val(x),left(NULL),right(NULL){}
// };
class Solution {
public:
// 定义中序遍历函数
void Traversal( TreeNode* cur , vector<int>& vec){
if ( cur == NULL){
return;
}
Traversal( cur -> left,vec);
vec.push_back( cur->val );
Traversal( cur -> right,vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
Traversal( root , result);
return result;
}
};
//迭代法的中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
// C++实现二叉树
// struct TreeNode{
// int val;
// TreeNode* left;
// TreeNode* right;
// TreeNode( int x):val(x),left(NULL),right(NULL){}
// };
class Solution {
public:
// // 定义中序遍历函数
// void Traversal( TreeNode* cur , vector<int>& vec){
// if ( cur == NULL){
// return;
// }
// Traversal( cur -> left,vec);
// vec.push_back( cur->val );
// Traversal( cur -> right,vec);
// }
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while( cur != NULL || !st.empty()){
if ( cur != NULL){
//指针访问节点，访问到最底层
st.push(cur);//将访问的节点放进栈
cur = cur->left; //左
}else{
cur = st.top();//从栈里弹出的数据，就是要处理的数据
st.pop();
result.push_back(cur->val); //中
cur = cur->right; //右
}
}
return result;
}
};
统一迭代法没看，二刷看