首页 > 代码库 > 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.
分析：这道题是pre-order traversal的变种，我们可以很容易的写出recursion的解法，先flatten左子树再flatten右子树，然后将左子树最右节点的right child设为右子树的根。但空间复杂度为O(logn)。代码如下：
class Solution {public: void flatten(TreeNode *root) { if(root == NULL) return; flatten(root->left); flatten(root->right); if(root->left == NULL) return; TreeNode *p = root->left; for(; p->right; p = p->right);//find right most node in left child tree p->right = root->right; root->right = root->left; root->left = NULL; }};
如果要用in place的方法，我们可以联想到Morris遍历。代码如下：
class Solution {public: void flatten(TreeNode *root) { TreeNode *cur = root; while(cur){ if(cur->left != NULL){ TreeNode *prev = cur->left; for(; prev->right && prev->right != cur; prev = prev->right); if(prev->right == NULL){ prev->right = cur; cur = cur->left; }else{ prev->right = cur->right; cur->right = cur->left; cur->left = NULL; cur = prev->right; } }else{ cur = cur->right; } } }};
Leetcode:Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。