114. 二叉樹展開為鏈表

給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：

  • 展開後的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。
  • 展開後的單鏈表應該與二叉樹 先序遍歷 順序相同。

 

示例 1：

Java練習題—二叉樹（七十二）_前序遍歷

輸入：root = [1,2,5,3,4,null,6]
輸出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

輸入：root = []
輸出：[]


方法一：前序遍歷

將二叉樹展開為單鏈表之後，單鏈表中的節點順序即為二叉樹的前序遍歷訪問各節點的順序。因此，可以對二叉樹進行前序遍歷，獲得各節點被訪問到的順序。由於將二叉樹展開為鏈表之後會破壞二叉樹的結構，因此在前序遍歷結束之後更新每個節點的左右子節點的信息，將二叉樹展開為單鏈表。


Java實現代碼：
class Solution {
    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);
        }
    }
}
python實現代碼：
class Solution:
    def flatten(self, root: TreeNode) -> None:
        preorderList = list()

        def preorderTraversal(root: TreeNode):
            if root:
                preorderList.append(root)
                preorderTraversal(root.left)
                preorderTraversal(root.right)
        
        preorderTraversal(root)
        size = len(preorderList)
        for i in range(1, size):
            prev, curr = preorderList[i - 1], preorderList[i]
            prev.left = None
            prev.right = curr