首页 > 代码库 > Flatten Binary Tree to Linked List
Flatten Binary Tree to Linked List
Problem Description:
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.
/** * Definition for binary tree * 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; while (root != NULL) { if (root->left != NULL) { TreeNode *p = root->left; while (p->right != NULL) <span style="font-family: Arial, Helvetica, sans-serif;">//找到左孩子的最右边节点</span> { p = p->right; } p->right = root->right; root->right = root->left; root->left = NULL; } root = root->right; } } };
思路二:可以看出变换后的树实际上是按照先序遍历的顺序排列的,因此可以利用中序递归遍历,记录先序遍历的前驱结点,依次调整每个孩子的左右子树,这里需要注意的是遍历过程中需要先将当前节点的右子树记录下来,再调整当前节点的左右子树,然后递归调整左右子树。具体代码如下:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *pre=NULL; void flatten(TreeNode *root) { if(root==NULL) return; TreeNode *lastright=root->right;//记录当前节点的右子树 if(pre) { pre->left=NULL; pre->right=root; } pre=root; flatten(root->left); flatten(lastright); } };
Flatten Binary Tree to Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。