【题目】
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like: 1
\
2
\
3
\
4
\
5
\
6
【分析】
在先序遍历的过程中把二叉树转为链表。
用pre记住当前节点的前一节点。节点的右指针作为链表指针,同时左指针赋空(第一次wrong就是因为没赋空)。
pre->right = p进行连接
【代码】
/*********************************
* 日期:2014-12-24
* 作者:SJF0115
* 题目: 114.Flatten Binary Tree to Linked List
* 来源:https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void flatten(TreeNode *root) {
if(root == NULL){
return;
}//if
// 入栈
stack<TreeNode *> stack;
stack.push(root);
TreeNode *p,*pre = NULL;
// 遍历
while(!stack.empty()){
// 出栈
p = stack.top();
stack.pop();
// 右子节点不空压入栈中
if(p->right){
stack.push(p->right);
}
// 左子节点不空压入栈中
if(p->left){
stack.push(p->left);
}
// 转换为链表
// 右子节点指针作为链表指针
p->left = NULL;
if(pre != NULL){
pre->right = p;
}//if
pre = p;
}//while
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
// 输出
void Display(TreeNode *root){
if(root == NULL){
return;
}//if
TreeNode *p = root;
while(p->right){
cout<<p->val<<"->";
p = p->right;
}//while
cout<<p->val<<endl;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
solution.flatten(root);
Display(root);
}
【代码二】
class Solution {
public:
void flatten(TreeNode *root) {
if(root == NULL){
return;
}//if
TreeNode *pre = NULL;
flatten(root,pre);
}
private:
void flatten(TreeNode *node,TreeNode *&pre){
if(node == NULL){
return;
}//if
// 记住右子节点
TreeNode *rightNode = node->right;
// 记住左子节点
TreeNode *leftNode = node->left;
// 转换为链表
if(pre != NULL){
pre->right = node;
pre->left = NULL;
}
pre = node;
// 左子树
if(leftNode){
flatten(leftNode,pre);
}
// 右子树
if(rightNode){
flatten(rightNode,pre);
}
}
};
因为节点的右指针用作链表指针,所以说二叉树在转换为链表时,节点右指针可能会被修改,用rightNode记住右指针。
【代码三】
class Solution {
public:
void flatten(TreeNode *root) {
if(root == NULL){
return;
}//if
flatten(root->left);
flatten(root->right);
if (root->left == NULL) {
return;
}//if
// 三方合并,将左子树所形成的链表插入到 root 和 root->right 之间
TreeNode *p = root->left;
// 寻找左链表最后一个节点
while(p->right) {
p = p->right;
}//while
p->right = root->right;
root->right = root->left;
root->left = NULL;
}
};
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
leetcode做过的LeetCode的题目记录一下。对一些比较经典的题型进行分类总结。数据结构 数组 字符串 队列 链表 双指针 栈 堆 树 二叉搜索树 字典树 线段树 并查集 哈希表 图基础... Flatten Binary Tree to Linked List
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
Leetcode 题解.pdf
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 后端.zip
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
Leetcode101.zip
My Solutions to Leetcode problems. All solutions support C
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
刷leetcode总结.md
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...