<abbr id="aeoko"></abbr>

[LeetCode] Flatten Binary Tree to Linked List

lowett 發(fā)布于2019-08-16 10:34 / 1538人閱讀

摘要：思路這題相當(dāng)于是當(dāng)?shù)臅r候，關(guān)鍵是要知道要被連接的的前面的一個這樣才可以把接上。用一路做到底，當(dāng)做到的時候，左邊返回右邊也返回，這時返回自己成為同樣接著繼續(xù)做。

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)

思路

這題相當(dāng)于是merge two LinkedList, 當(dāng)merge linkedList的時候，關(guān)鍵是要知道要被連接的ListNode的前面的一個ListNode, 這樣才可以把Listnode.next接上。用divide-conquer一路做到底，當(dāng)做到Leaf node的時候，左邊返回Null, 右邊也返回null，這時返回自己,成為leftLast, 同樣接著繼續(xù)做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;
}