首页 > 代码库 > leetcode - Flatten Binary Tree to Linked List
leetcode - Flatten Binary Tree to Linked List
题目: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 6
The flattened tree should look like:
1 2 3 4 5 6
click to show hints.
Hints:View CodeView Code
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
个人思路:
1、创建一个队列,把节点按照先序遍历的顺序入队
2、把节点挨个出队,前一个出队节点是后一个出队节点的父节点,后一个出队节点是前一个出队节点的右孩子节点,且每个非叶节点的左孩子为空
代码:
1 #include <stddef.h> 2 #include <iostream> 3 #include <queue> 4 5 using namespace std; 6 7 struct TreeNode 8 { 9 int val;10 TreeNode *left;11 TreeNode *right;12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18 void flatten(TreeNode *root)19 {20 if (!root)21 {22 return;23 }24 25 queue<TreeNode *> preNodes;26 preorder(root, preNodes);27 root = preNodes.front();28 preNodes.pop();29 TreeNode * currentNode = root;30 while (!preNodes.empty())31 {32 TreeNode *tmp = preNodes.front();33 preNodes.pop();34 currentNode->right = tmp;35 currentNode->left = NULL;36 currentNode = currentNode->right;37 }38 }39 private:40 void preorder(TreeNode *root, queue<TreeNode *> &preNodes)41 {42 if (!root)43 {44 return;45 }46 preNodes.push(root);47 preorder(root->left, preNodes);48 preorder(root->right, preNodes);49 }50 };
在网上看到一个比较普遍的递归算法,链接:http://blog.unieagle.net/2012/12/16/leetcode-problemflatten-binary-tree-to-linked-list/,里面有比较详细的思路解析,可以参考,大致思路是这样:要扁平化一棵树,则扁平化根节点的左子树和右子树,然后将左子树放到根节点的右孩子位置,右子树放到左子树的叶节点的右孩子位置
代码:
1 #include <stddef.h> 2 #include <iostream> 3 #include <queue> 4 5 using namespace std; 6 7 struct TreeNode 8 { 9 int val;10 TreeNode *left;11 TreeNode *right;12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18 void flatten(TreeNode *root)19 {20 /*21 if (!root)22 {23 return;24 }25 26 queue<TreeNode *> preNodes;27 preorder(root, preNodes);28 root = preNodes.front();29 preNodes.pop();30 TreeNode * currentNode = root;31 while (!preNodes.empty())32 {33 TreeNode *tmp = preNodes.front();34 preNodes.pop();35 currentNode->right = tmp;36 currentNode->left = NULL;37 currentNode = currentNode->right;38 }39 */40 41 if (!root)42 {43 return;44 }45 if (root->left)46 {47 flatten(root->left);48 }49 if (root->right)50 {51 flatten(root->right);52 }53 if (!root->left)54 {55 return;56 }57 58 TreeNode *left_leaf = root->left;59 while (left_leaf->right)60 {61 left_leaf = left_leaf->right;62 }63 left_leaf->right = root->right;64 root->right = root->left;65 root->left = NULL;66 }67 private:68 void preorder(TreeNode *root, queue<TreeNode *> &preNodes)69 {70 if (!root)71 {72 return;73 }74 preNodes.push(root);75 preorder(root->left, preNodes);76 preorder(root->right, preNodes);77 }78 };
链接中还有一个非递归的思路,大家也可以看看
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。