首页 > 代码库 > [LeetCode]114.Flatten Binary Tree to Linked List
[LeetCode]114.Flatten Binary Tree to Linked List
【题目】
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / 2 5 / \ 3 4 6The 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 =http://www.mamicode.com/= -1){>【代码二】
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; } };
[LeetCode]114.Flatten Binary Tree to Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。