首页 > 代码库 > [LeetCode] Flatten Binary Tree to Linked List
[LeetCode] 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:
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
思路一:递归的思想。使用后序递归的方法。先将左右子树转换为链表，再将左右子树连接
时间复杂度O(n),空间复杂度O(logN)
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 void flatten(TreeNode *root) {13 if (root == nullptr) return;14 15 flatten(root->left);16 flatten(root->right);17 18 //三方合并，将左子树形成的链表插入到root和root->right之间19 TreeNode *p = root->right;20 while (p->right) p = p->right;21 p->right = root->right;22 root->right = root->left;23 root->left = nullptr;24 }25 };
思路二：迭代的方法。依据题目与前序遍历之间的关系。使用前序遍历的方法。
1 void flatten(TreeNode *root) { 2 if(root == NULL) return; 3 while(root){ 4 if(root->left){ 5 TreeNode *pre = root->left; 6 while(pre->right) 7 pre = pre->right; 8 pre->right = root->right; 9 root->right = root->left;10 root->left = NULL;11 }12 root = root->right;13 }14 }
[LeetCode] Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。