Description

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

tree

The flattened tree should look like:

flattened

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Solution

DFS

平凡的寫法。注意要將root的左右節(jié)點(diǎn)置為null，再向下面遞歸！否則下面的遞歸會改變root的結(jié)構(gòu)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode tail;
    
    public void flatten(TreeNode root) {
        dfs(root);
    }
    
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (tail != null) { 
            tail.right = root;
        }
        tail = root;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = null;
        
        dfs(left);
        dfs(right);
    }
}

Iterative, time O(n), space O(1)

通過掛載左子樹到右邊來實(shí)現(xiàn)，很妙啊。

上面是題目及提示信息，大概意思是要按照前序遍歷的順序，將其變成一個單鏈表（但還是用樹結(jié)構(gòu)存），OK，開始分析下：

按照題目要求，它要把左子樹的所有節(jié)點(diǎn)按照前序的順序，掛載在右子樹的鏈表中，那么我們首先遇到的第一個問題，把左子樹掛載在右邊，那之前的跟節(jié)點(diǎn)的右子樹怎么處理？

上面這個問題，可以這樣思考，我們假設(shè)已經(jīng)把左子樹掛載在右邊，先忽視之前根節(jié)點(diǎn)的右子樹，那么現(xiàn)在需要把其加載進(jìn)去，那顯然按照前序遍歷的思想，我們肯定是把右子樹掛載在左子樹的某個位置，使得前序遍歷時右子樹在左子樹之后被遍歷到，那么只需要將右子樹掛載到左子樹的right most節(jié)點(diǎn)即可（其實(shí)掛載到其他地方也行，只要保證前序遍歷順序不變即可），OK，這是我們目前的想法。

再思考下，我們只是簡單的將根節(jié)點(diǎn)的左子樹掛載在它和它的右子樹中間，并沒有將其“捋平”，這樣就涉及到遞歸的處理，反復(fù)的將其，加進(jìn)去。那這樣就涉及到剛開始的一個問題，我們是否真的需要把右子樹擱在左子樹前序遍歷的最后一個元素中？如下圖所示，這里顯然，我們只需要將4 擱在2的右子樹位置上，（第二張圖），然后再遞歸的捋順根節(jié)點(diǎn)的right即可。

image.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null) {
                TreeNode rightMostInLeft = root.left;
                while (rightMostInLeft.right != null) {
                    rightMostInLeft = rightMostInLeft.right;
                }
                // mount root.right to rightMostInLeft
                // and mount root.left to root.right
                rightMostInLeft.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            
            root = root.right;
        }
    }
}