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
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
题目要求按照前序遍历转换成一个链表。
思路：先递归实现左右子树，然后调整指针连接起来。 时间复杂度O(N)，每个节点最多访问2次，一次flat，一次findRightMost。 空间复杂度O(N).
思路2: 基于 Moris Traveral。O(N) 时间，O(1)空间。
public class Solution { public void flatten(TreeNode root) { if (root == null) return; flatten(root.left); flatten(root.right); TreeNode p = root; if (p.left == null) return; else p = p.left; while (p.right != null) p = p.right; p.right = root.right; root.right = root.left; root.left = null; } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); root.right = new TreeNode(5); root.right.right = new TreeNode(6); new Solution().flatten(root); ; } }
思路2
class Solution { public void flatten(TreeNode root) { // Handle the null scenario if (root == null) { return; } TreeNode node = root; while (node != null) { // If the node has a left child if (node.left != null) { // Find the rightmost node TreeNode rightmost = node.left; while (rightmost.right != null) { rightmost = rightmost.right; } // rewire the connections rightmost.right = node.right; node.right = node.left; node.left = null; } // move on to the right side of the tree node = node.right; } } }
第二遍记录：
public class Solution { public void flatten(TreeNode root) { if(root==null) return; flatten(root.left); flatten(root.right); if(root.left==null) return; TreeNode leftEnd=root.left; while(leftEnd.right != null) leftEnd=leftEnd.right; leftEnd.right=root.right; root.right=root.left; root.left=null; } }
第三遍记录：
先递归flaten左右子树，然后根据左右子树（尤其是左子树）的情况，构造链表，最后注意把当前节点的left指针置为null
public class Solution { public void flatten(TreeNode root) { flat(root); } private TreeNode flat(TreeNode root) { if (root == null) return null; TreeNode left = flat(root.left); TreeNode right = flat(root.right); if (left == null) return root; root.right = left; TreeNode leftEnd = left; while (leftEnd.right != null) { leftEnd = leftEnd.right; } leftEnd.right = right; //don't forget this root.left = null; return root; } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); root.right = new TreeNode(5); root.right.right = new TreeNode(6); new Solution().flatten(root); ; } }
参考：