Day20-二叉树-二叉树转单链表
Day20-二叉树-二叉树转单链表
一 唠嗑
还唠啥唠
二 上题！
Q：给定一个二叉树，以前序遍历的顺序，将其原地转换成单链表
举例：网上找个二叉树
那么结果应该为：1->2->3->4->5->6
三 冷静分析
这道题如果用投机取巧的办法：前序遍历二叉树，将节点push进一个vector中，再遍历vector中的节点，将相邻的节点连接上，成为单链表。面试官可能也不会打断你，所以我在代码中也同样给出了该方法。
但要知道这并不满足"原地"这个条件。
那面试官如果说：这方法可以，但是还有更好的，不用申请额外空间的算法吗？
所以，怎么原地呢？
我们可以这样考虑：
1.在处理递归时，我们无须想明白从头到尾的递归过程，只需要考虑清楚，处在某一阶段下，如何递归。有点像数学归纳法的假设n=k成立时，证明n=k+1也成立
2.在某一时刻，我们已经得到了如下的结果：
根节点 【1】
左子树链表 【2，3，4】
右子树链表 【5，6】
3.因为树中的节点，有left，right，两个指针。而最终的单链表每个节点只需要一个指针，所以我们统一舍弃left，用right指针将节点相连。
4.将1与2相连，4与5相连，不就是单链表了吗
所以，又回到单链表问题的精髓了：关键节点。
很显然，4就是关键节点。
即递归的过程中，我们需要传引用，来时刻给出左子树的尾节点，即4的位置，我在代码中用last指针，时刻指向这个尾节点。同理，由于是递归思想，也要时刻给出右子树的尾节点。
5.完事，齐活，我们只要处理好中间某个时刻的逻辑，剩下的事，交给递归做，就好~
6.建议跟着代码，画个图，走一遍，你就明白递归的神奇了
四 完整代码及十分十分十分详细的注释
//
// Created by renyi on 2019-07-08.
//
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : value(v), left(NULL), right(NULL) {}
};
//先写通过申请额外空间的算法，比较简单，不写注释了
void preOrderExtraSpace(TreeNode* root, vector<TreeNode*> &nodeVec){
if (!root){
return;
}
nodeVec.push_back(root);
preOrderExtraSpace(root->left, nodeVec);
preOrderExtraSpace(root->right, nodeVec);
}
void flattenExtraSpace(TreeNode* root){
vector<TreeNode*> nodeVec;//初始化一个存放节点的数组
preOrderExtraSpace(root, nodeVec);
for (int i = 1; i < nodeVec.size(); i++) {
nodeVec[i-1]->left = nullptr;//左指针赋值空，右指针指向后面的节点，即将节点链起来
nodeVec[i-1]->right = nodeVec[i];
}
}
//接下来是不申请额外空间，原地将二叉树转单链表
void preOrder(TreeNode* root, TreeNode*& last){//last指针传引用是为了，传给下一次递归用
if (!root){
return;
}
if (!root->left && !root->right){//如果是叶子节点，那它就是last指针
last = root;//如果左右都是叶子，那last最终会递归到，最后边的叶子
return;//如果左右只有一个叶子，那last就是叶子
}
TreeNode* left = root->left;//备份左右指针
TreeNode* right = root->right;
TreeNode* leftLast = nullptr;
TreeNode* rightLast = nullptr;
if (left){//如果有左子树，就先一路递归左子树，直到叶子节点
preOrder(left, leftLast);
root->left = nullptr;//当前节点的左指针赋空，统一用右指针root->right连接成单链表
root->right = left;//这个left就是出递归的left，就是左子树（如果有左子树）的叶子节点
last = leftLast;//将出递归的leftLast,赋值给last指针，以进行后面的递归
}
if (right){//如果有右子树，就继续递归右子树
preOrder(right, rightLast);
if (leftLast){//如果有leftLast，就说明进行了上面的if里面的递归，即说明，有左子树，并且leftLast是左子树的叶子节点
leftLast->right = right;//将左子树的叶子节点的后继，指向右子树，即完成链表的连接步骤
}
last = rightLast;//将右子树（如果有右子树）出递归时的rightLast赋给last，来进行后面的递归
}
}
void flatten(TreeNode* root){
TreeNode* last = nullptr;
preOrder(root, last);
}
int main(){
TreeNode a(1);//建立配图的二叉树
TreeNode b(2);
TreeNode c(5);
TreeNode d(3);
TreeNode e(4);
TreeNode f(6);
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.right = &f;
flatten(&a);
TreeNode* head = &a;
while (head){
if (head->left){
printf("ERROR\n");
} else{
printf("[%d]", head->value);
head = head->right;
}
}
printf("\n");
return 0;
}运行结果
