首页 > 代码库 > [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
思路：
先序遍历的变形，有两种方法。一种从上往下，一种从下往上。
先说从上往下。从根节点开始，将当前节点的坐节点移到右节点上，原来的右节点与现在的最右节点相连。这样，当前节点的左边就为NULL，并且它的右节点就是先序遍历接下来应该访问的值。
在说从下往上。对某个节点进行操作，先假设右边全部有序（所以先递归右节点），其余的和从上往下一样，只是这种方法先递归到树中最右节点，再开始操作。
题解：
/** * 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; if(root->left) { TreeNode *tmp = root->right; root->right = root->left; root->left = NULL; TreeNode *LastRight = root; while(root->right) root = root->right; root->right = tmp; root = LastRight; } flatten(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: void flatten(TreeNode *root) { if(root==NULL) return; if(root->left==NULL && root->right==NULL) return; flatten(root->right); flatten(root->left); TreeNode *tmp = root->right; if(root->left) { root->right = root->left; root->left = NULL; while(root->right) root = root->right; root->right = tmp; } }};
[leetcode] Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。