114_二叉樹展開為連結清單

114_二叉樹展開為連結清單

package 二叉樹.BT;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 * @author Huangyujun
 *
 * 程式設計裡有很重要的一個思維：就是記錄“第一次的結果”，然後等到走到“第二次的結果”時進行一些操作
 * 可能式第二次的結果與第一次進行比較，
 * 也可能是（比較之後）将第二次結果覆寫掉第一次結果
 * 是以程式設計裡非常重要的變量：标記變量：即記錄“第一次的結果”（前一次的結果），留個“第二次的結果”（目前的結果）進行比較
 */
public class _114_二叉樹展開為連結清單 {
    public class TreeNode        {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //題意：左指針變成null，右指針指向下個結點（不斷取出目前結點，跟下一個結點
    //題目給提示了呀：“展開後的單連結清單應該與二叉樹 先序周遊 順序相同。” 
    //咱就利用先序周遊的遞歸或者疊代周遊到每個結點，将其添加到list 集合中，（為什麼要添加到List 而不直接操作：）
    //理由：咱需要重塑一顆樹的形狀呀（不是你想變就能變）
    //然後咱再周遊每個結點，将其左指針指向null，右指針指向下個結點（建構對外連結式形狀）
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
    

//題意：左指針變成null，右指針指向下個結點
//記錄第一個結點prevNode：
//然後 走到第二個結點currNode，讓第一個結點prev 的左指針指向null，右指針 指針 第二個結點
    public void flatten2(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.push(root);
        TreeNode prev = null;
        while (!queue.isEmpty()) {
            TreeNode curr = queue.pop();
            if (prev != null) {    //通過 prev != null 判斷得知：目前結點是第二個（來到了下一次）啦
                prev.left = null;
                prev.right = curr;
            }
            TreeNode left = curr.left, right = curr.right;
            if (right != null) {
                queue.push(right);
            }
            if (left != null) {
               queue.push(left);
            }
            prev = curr;    //記錄第一次“前一次的結果”
        }
    }
  
}