首页 > 代码库 > Cracking-- 17.13 将二叉树转换成双向链表
Cracking-- 17.13 将二叉树转换成双向链表
在书的105页
使用中根遍历的思想
left 之后 为 root 之后 为 right
则对左子树来说
left->right = root; root->left = left;
对右子树来说
root->right = right-> -> -> left;
left->left 为根的根 的根
而right->left 则为直接的根
#include <iostream>#include <vector>using namespace std; struct node { int val; node *left; node *right; node(int _val){ val = _val; left = NULL; right = NULL; }};node* change(node *root){ if(root == NULL) return NULL; node *retNode = NULL; if(root->left == NULL && root->right == NULL) { return root; } if(root->left) { retNode = change(root->left ); retNode->right = root; root->left = retNode; retNode = root; } if(root->right) { retNode = change(root->right); node* tmp = retNode; while(tmp->left) tmp = tmp->left; root->right = tmp; tmp->left = root; } return retNode;}int main(){ node *n1 = new node(12); node *n2 = new node(8); node *n3 = new node(15); node *n4 = new node(6); node *n5 = new node(10); node *n6 = new node(13); node *n7 = new node(20); n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; n3->left = n6; n3->right = n7; node *ans; ans = change(n1); return 0;}
Cracking-- 17.13 将二叉树转换成双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。