二叉树
https://www.acwing.com/solution/content/12969/
#include <iostream>
#include <vector>
using namespace std;
int k = 0;
string str; // 输入的字符串表示二叉树的每个节点的值，当遇到 '.' 时结束输入 dfsfsd.
vector<char> in, post;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(){
char ch = str[k ++];
if (ch == '.') return NULL;
TreeNode* node = new TreeNode(ch);
node->left = buildTree();
node->right = buildTree();
return node;
}
void inorder(TreeNode* root) {
if (root == NULL) return ;
inorder(root->left);
in.push_back(root->val);
inorder(root->right);
}
/*
void dfs1(TreeNode* root) {
if (!root) return ;
dfs1(root->left);
in.push_back(root->val);
dfs1(root->right);
}
void dfs2(TreeNode* root) {
if (!root) return ;
dfs2(root->left);
dfs2(root->right);
post.push_back(root->val);
}
vector<char> inorder(TreeNode* root) {
dfs1(root);
return in;
}
vector<char> postorder(TreeNode* root) {
dfs2(root);
return post;
}
*/
void postorder(TreeNode* root) {
if (root == NULL) return ;
postorder(root->left);
postorder(root->right);
post.push_back(root->val);
}
int main () {
cin >> str;
int n = str.size();
TreeNode* root = buildTree();
inorder(root);
postorder(root);
for (int i = 0; i < in.size(); i ++) cout << in[i] << ' ';
cout << endl;
for (int i = 0; i < post.size(); i ++) cout << post[i] << ' ';
cout << endl;
return 0;
}
/*
输入
ABE..D..CF.K...
输出
E B D A F K C
E D B K F C A
*/
构建二叉树，递归方法得到遍历结果
import java.util.*;
class TreeNode{
TreeNode left,right;
char val;
TreeNode(char x){
this.val=x;
}
}
class Main{
static StringBuilder in=new StringBuilder();
static StringBuilder post=new StringBuilder();
static int k;
static char[] ch;
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
ch=s.toCharArray();
TreeNode tree=buildTree();
inorder(tree);
postorder(tree);
System.out.println(in);
System.out.println(post);
}
public static TreeNode buildTree(){
char root=ch[k++];
if(root=='.') return null;
TreeNode node=new TreeNode(root);
node.left=buildTree();
//in.append(root);
node.right=buildTree();
//post.append(root);
return node;
}
//递归写法
public static void inorder(TreeNode node){//中序
if(node==null) return;
inorder(node.left);
in.append(node.val);
inorder(node.right);
}
public static void postorder(TreeNode node){//后序
if(node==null) return;
postorder(node.left);
postorder(node.right);
post.append(node.val);
}
}
作者：Ivy
链接：https://www.acwing.com/solution/content/12969/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
构建二叉树，非递归方法得到遍历结果
import java.util.*;
class TreeNode{
TreeNode left,right;
char val;
TreeNode(char x){
this.val=x;
}
}
class Main{
static StringBuilder in=new StringBuilder();
static StringBuilder post=new StringBuilder();
static int k;
static char[] ch;
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
ch=s.toCharArray();
TreeNode tree=buildTree();
inorder(tree);
postorder(tree);
System.out.println(in);
System.out.println(post);
}
public static TreeNode buildTree(){
char root=ch[k++];
if(root=='.') return null;
TreeNode node=new TreeNode(root);
node.left=buildTree();
//in.append(root);
node.right=buildTree();
//post.append(root);
return node;
}
////递归写法
// public static void inorder(TreeNode node){//中序
// if(node==null) return;
// inorder(node.left);
// in.append(node.val);
// inorder(node.right);
// }
// public static void postorder(TreeNode node){//后序
// if(node==null) return;
// postorder(node.left);
// postorder(node.right);
// post.append(node.val);
// }
////非递归写法
public static void inorder(TreeNode node){//中序
Stack<TreeNode> st=new Stack<>();
TreeNode cur=node;
while(cur!=null||!st.isEmpty()){
while(cur!=null){
st.push(cur);
cur=cur.left;
}
if(!st.isEmpty()){
cur=st.pop();
in.append(cur.val);
cur=cur.right;
}
}
}
public static void postorder(TreeNode node){//逆后序 根 右 左
Stack<TreeNode> st=new Stack<>();
TreeNode cur=node;
while(cur!=null||!st.isEmpty()){
while(cur!=null){
st.push(cur);
post.append(cur.val);
cur=cur.right;
}
if(!st.isEmpty()){
cur=st.pop();
cur=cur.left;
}
}
post.reverse();
}
}
作者：Ivy
链接：https://www.acwing.com/solution/content/12969/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
链表
https://www.acwing.com/file_system/file/content/whole/index/content/2870240/
举栗子：
剑指 Offer II 021. 删除链表的倒数第 n 个结点
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) :val(x), next(nullptr) {}
};
ListNode* create()
{
auto dummy = new ListNode(-1), cur = dummy;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
auto p = new ListNode(x);
cur = cur->next = p;
}
auto head = dummy->next;
delete dummy;
return head;
}
void print(ListNode *head)
{
for (auto p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
}
ListNode* deleteKthFromEnd(ListNode* head, int k)
{
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
for (int i = 0; i < n - k; i ++ ) p = p->next;
auto tmp = p->next;
p->next = p->next->next;
delete tmp;
head = dummy->next;
delete dummy;
return head;
}
int main()
{
cin >> n >> k; //n是链表中结点个数, k是待删除链表中倒数第k个结点
ListNode* head = create();
print(head);
head = deleteKthFromEnd(head, k);
print(head);
return 0;
}
单向和双向
https://www.acwing.com/blog/content/119/
单链表举例
#include <iostream>
using namespace std;
int n;
struct ListNode {
int val;
ListNode *next;
// ListNode(int x) : val(x), next(NULL) {}
ListNode(int x) {
val = x;
next = NULL;
}
};
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto a = dummy;
for (int i = 0; i < left - 1; i ++) a = a->next;
auto b = a->next, c = b->next;
for (int i = 0; i < right - left; i ++) {
auto d = c->next;
c->next = b;
b = c, c = d;
}
a->next->next = c;
a->next = b;
return dummy->next;
}
void print(ListNode* head) {
for (auto p = head; p; p = p->next) cout << p->val << ' ';
cout << endl;
}
ListNode* create() {
auto dummy = new ListNode(-1), cur = dummy;
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
auto p = new ListNode(x);
cur = cur->next = p;
}
auto head = dummy->next;
delete dummy;
return head;
}
int main () {
int l, r;
cin >> n >> l >> r;
ListNode* head = create();
print(head);
head = reverseBetween(head, l, r);
print(head);
return 0;
}
输入
6 3 6
6 2 3 4 5 -1
输出
6 2 3 4 5 -1
6 2 -1 5 4 3
双向链表的 操作：未整理完，还有问题
#include <iostream>
using namespace std;
int n;
struct Node {
int val;
Node* next, *prev;
Node() : next(NULL), prev(NULL) {}
Node(int _val) : val(_val), next(NULL), prev(NULL) {}
};
void print(Node* head) {
for (auto p = head; p; p = p->next) cout << p->val << ' ';
cout << endl;
}
// 双向链表的插入的操作
void insert(Node* p, int x) { // 往p节点后面插入一个值为x的节点
auto q = new Node(x);
q->next = p->next;
q->prev = p;
p->next->prev = q;
p->next = q;
}
void _delete(Node *p) {
p->next->prev = p->prev;
p->prev->next = p->next;
delete p;
}
Node* create(int n) {
Node* head = new Node(), *tail = new Node();
head->next = tail, tail->prev = head;
while (n --) {
int x;
cin >> x;
insert(head, x);
}
return head->next;
}
int main () {
cin >> n; // 建立n个节点的双向链表
Node* head = new Node(), *tail = new Node();
head->next = tail, tail->prev = head;
print(head);
Node* double_list = create(n);
print(head);
return 0;
}
