【問題描述】[中等]

【解答思路】

1. 前序遍歷

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

時間復雜度：O(N) 空間復雜度：O(N)

遞歸（自上而下）

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);}} }

迭代
時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public void flatten(TreeNode root) {List<TreeNode> list = new ArrayList<TreeNode>();Deque<TreeNode> stack = new LinkedList<TreeNode>();TreeNode node = root;while (node != null || !stack.isEmpty()) {while (node != null) {list.add(node);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}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;}} }

2. 前序遍歷和展開同時進行

時間復雜度：O(N) 空間復雜度：O(N）

class Solution {public void flatten(TreeNode root) {if (root == null) {return;}Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);TreeNode prev = null;while (!stack.isEmpty()) {TreeNode curr = stack.pop();if (prev != null) {prev.left = null;prev.right = curr;}TreeNode left = curr.left, right = curr.right;//先右后左if (right != null) {stack.push(right);}if (left != null) {stack.push(left);}prev = curr;}} }

3. 前驅節點

前兩種方法都借助前序遍歷，前序遍歷過程中需要使用棧存儲節點。有沒有空間復雜度是 O(1)O(1) 的做法呢？

注意到前序遍歷訪問各節點的順序是根節點、左子樹、右子樹。如果一個節點的左子節點為空，則該節點不需要進行展開操作。如果一個節點的左子節點不為空，則該節點的左子樹中的最后一個節點被訪問之后，該節點的右子節點被訪問。該節點的左子樹中最后一個被訪問的節點是左子樹中的最右邊的節點，也是該節點的前驅節點。因此，問題轉化成尋找當前節點的前驅節點。

步驟
對于當前節點，如果其左子節點不為空，則在其左子樹中找到最右邊的節點，作為前驅節點，將當前節點的右子節點賦給前驅節點的右子節點，然后將當前節點的左子節點賦給當前節點的右子節點，并將當前節點的左子節點設為空。對當前節點處理結束后，繼續處理鏈表中的下一個節點，直到所有節點都處理結束。

時間復雜度：O(N) 空間復雜度：O(1)

class Solution {public void flatten(TreeNode root) {TreeNode curr = root;while (curr != null) {if (curr.left != null) {TreeNode next = curr.left;TreeNode predecessor = next;while (predecessor.right != null) {predecessor = predecessor.right;}predecessor.right = curr.right;curr.left = null;curr.right = next;}curr = curr.right;}} }

遞歸寫法

1/ \2 5/ \ \ 3 4 6//將 1 的左子樹插入到右子樹的地方1\2 5/ \ \3 4 6 //將原來的右子樹接到左子樹的最右邊節點1\2 / \ 3 4 \5\6//將 2 的左子樹插入到右子樹的地方1\2 \ 3 4 \5\6 //將原來的右子樹接到左子樹的最右邊節點1\2 \ 3 \4 \5\6

遞歸版本

相應的左孩子也要置為 null，同樣的也不用擔心左孩子丟失，因為是后序遍歷，左孩子已經遍歷過了

private TreeNode pre = null;public void flatten(TreeNode root) {if (root == null)return;flatten(root.right);flatten(root.left);root.right = pre;root.left = null;pre = root; }

【總結】

1. 解法一二 自頂向下 解法三 自底向上

2.List接口常用方法

// 1、將指定的元素,添加到該集合中的指定位置上。 public void add(int index, E element)// 2、返回集合中指定位置的元素。 public E get(int index)// 3、移除列表中指定位置的元素,返回的是被移除的元素。 public E remove(int index)// 4、用指定元素替換集合中指定位置的元素,返回值的更新前的元素。 public E set(int index, E element)

3.遞歸

在實現遞歸函數之前，有兩件重要的事情需要弄清楚:

遞推關系：一個問題的結果與其子問題的結果之間的關系。
基本情況：不需要進一步的遞歸調用就可以直接計算答案的情況。可理解為遞歸跳出條件。
一旦我們計算出以上兩個元素，再想要實現一個遞歸函數，就只需要根據遞推關系調用函數本身，直到其抵達基本情況。

轉載鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/

參考鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–26/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[Leetcode][第114题][JAVA][二叉树展开为链表][递归][迭代]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。