首页 > 代码库 > leetcode Flatten Binary Tree to Linked List
leetcode Flatten Binary Tree to Linked List
题目：给定一个棵树，将其转换成flattened tree。只有右节点的，类似于链表，且在原址操作。
例如：
Given
1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1 2 3 4 5 6
Hints:
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
根据提示发现flattened tree是按照前序遍历顺序排列的。
这题难度在于在原址操作，否则，中序遍历一下，构造一个树就可以了。
我是用递归的思想，一个子函数将传入的root变为flattened tree，并且返回该flattened tree的末尾节点。那么我们只要对根节点的左边做一个子函数处理，右边做一个子函数处理，然后把root的left赋值为right，将原来的right赋值为左边子函数处理后返回的末尾节点的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 *Tree2ListEnd(TreeNode *root){ if (!root) return NULL; if (!root -> left && !root -> right) return root; if (!root -> left) return Tree2ListEnd(root -> right); if (!root -> right) { root -> right = root -> left; root -> left = NULL; // 记得将左边赋值空 return Tree2ListEnd(root -> right); } if (root -> left && root -> right) { TreeNode *ri = root -> right; root -> right = root -> left; root -> left = NULL; // 左边赋值空 TreeNode *riEnd = Tree2ListEnd(root -> right); riEnd -> right = ri; return Tree2ListEnd(riEnd -> right); // 剩下的部分也要处理 }}void flatten(TreeNode *root){ if (!root || !root->left && !root->right) return ; if (!root -> left) flatten(root -> right); else { TreeNode *lfEnd = Tree2ListEnd(root -> left); Tree2ListEnd(root -> right); TreeNode *ri = root -> right; root -> right = root -> left; root -> left = NULL; // 记得赋值空 lfEnd -> right = ri; }}};
需要注意的地方如注释所写。
leetcode Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。