[LeetCode] Flatten Binary Tree to Linked List
文章目录
Flatten Binary Tree to Linked List
Flatten a binary tree to a fake "linked list" in pre-order traversal.
Here we use the right pointer in TreeNode as the next pointer in
ListNode.
Divide-Conquer
Time Complexity
O(n)
Space Complexity
O(logn)
思路
这题相当于是merge two LinkedList, 当merge linkedList的时候,关键是要知道要被连接的ListNode的前面的一个ListNode, 这样才可以把Listnode.next接上。用divide-conquer一路做到底,当做到Leaf node的时候,左边返回Null, 右边也返回null,这时返回自己,成为leftLast, 同样接着继续做rightLast。
第一种情况:if(leftLast == null && rightLast == null) return root;
第二种情况:if(leftLast != null && rightLast != null) 把左边返回上来的半边的LinkedList的最后一个与右边的第一个root.right接上,return rightLast作为新的leftLast
第三种情况:if(leftLast != null && rightLast == null) 还是要做与第二种情况同样的操作,但是返回的是leftLast
第四种情况if(leftLast == null && rightLast != null) return rightLast作为新的leftLast
所以第二种情况和第四种情况合并,但是如果rightLast != null还是要先返回rightLast
代码
public void flatten(TreeNode root) {
// write your code here
//corner case
if(root == null) return;
helper(root);
}
private TreeNode helper(TreeNode root){
if(root == null) return null;
TreeNode leftLast = helper(root.left);
TreeNode rightLast = helper(root.right);
if(leftLast == null && rightLast == null) return root; //leafnode
if(leftLast != null){
leftLast.right = root.right;
root.right = root.left;
root.left = null;
}
if(rightLast != null) return rightLast;
if(leftLast != null) return leftLast;
return root;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论