114. 二叉树展开为链表

linwt · linwt · commit 986c1f842745 · 2021-11-24T23:19:52.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -2,6 +2,7 @@
 101. 对称二叉树
 102. 二叉树的层序遍历
 104. 二叉树的最大深度
+114. 二叉树展开为链表
 144. 二叉树的前序遍历
 145. 二叉树的后序遍历
 226. 翻转二叉树
diff --git a/leetcode_Java/Solution0094.java b/leetcode_Java/Solution0094.java
@@ -109,9 +109,11 @@ public List<Integer> inorderTraversal(TreeNode root) {
 
 
 /*
-* 莫里斯遍历：用递归和迭代的方式都使用了辅助的空间，而莫里斯遍历的优点是没有使用任何辅助空间。
-* 缺点是改变了整个树的结构，强行把一棵二叉树改成一段链表结构。
-* 思路：把根节点接到左子树的最后一个右节点上，形成链表，再遍历获取链表的值
+* 1、莫里斯遍历：
+*    1）用递归和迭代的方式都使用了辅助的空间，而莫里斯遍历的优点是没有使用任何辅助空间。
+*    2）缺点是改变了整个树的结构，强行把一棵二叉树改成一段链表结构。
+* 2、思路：把根节点接到左子树的最后一个右节点上，形成链表，再遍历获取链表的值
+* 3、相似题：114.二叉树展开为链表，前序遍历
 * */
 class Solution {
     public List<Integer> inorderTraversal(TreeNode root) {
diff --git a/leetcode_Java/Solution0114.java b/leetcode_Java/Solution0114.java
@@ -0,0 +1,92 @@
+// 二叉树展开为链表
+
+
+/**
+ * Definition for a binary tree node.
+ * 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;
+ *     }
+ * }
+ */
+
+
+/*
+* 迭代思路：
+* 1、简单理解：把左子树塞到根节点和右节点中间，每个节点都要做同样的操作
+* 2、简单情况分析：
+*    1）根节点为空：直接返回列表
+*    2）只有根节点：将根节点的值存入列表，返回列表
+*    3）有根节点和左节点：将左节点移到右节点的位置，遍历右节点将值存入列表，返回列表
+*    4）有根节点和右节点：不用移动，遍历右节点将值存入列表，返回列表
+*    5）有根节点、左节点、右节点：将左节点移到根节点和右节点中间，遍历右节点将值存入列表，返回列表
+* 3、节点连接步骤：
+*    1）前序遍历是中左右，即根节点→左子树→右子树
+*    2）左子树遍历的最后一个节点是 左子树的最后一个右子节点，因此要将其连接到根节点的右节点上
+*    3）根节点的右指针要指向左节点，左指针指向空，从而形成中左右的链表
+* 4、遍历逻辑：
+*    1）根指针的移动代表着前序遍历的顺序，循环遍历条件是根指针不为空
+*    2）如果根节点的左节点不为空，则进行节点连接步骤；如果为空，则将节点值存入列表
+*    3）根节点处理完后看，根指针指向右节点，准备下一轮判断
+* 5、“144.二叉树的前序遍历”展开为链表的解法
+* */
+class Solution {
+    public List<Integer> flatten(TreeNode root) {
+        List<Integer> list = new ArrayList<>();
+        while (root != null) {
+            if (root.left != null) {
+                TreeNode pre = root.left;
+                while (pre.right != null) {
+                    pre = pre.right;
+                }
+                pre.right = root.right;
+                root.right = root.left;
+                root.left = null;
+            } else {
+                list.add(root.val);
+            }
+            root = root.right;
+        }
+        return list;
+    }
+}
+
+
+/*
+* 迭代思路：与上个解法相同。用队列/栈存储下一个要遍历的节点，替代了遍历指针，缺点是使用了多余的空间
+* */
+class Solution {
+    public List<Integer> flatten(TreeNode root) {
+        List<Integer> list = new ArrayList<>();
+        if (root == null) {
+            return list;
+        }
+        Queue<TreeNode> queue = new LinkedList<>();
+        queue.offer(root);
+        while (!queue.isEmpty()) {
+            root = queue.poll();
+            if (root.left != null) {
+                TreeNode pre = root.left;
+                while (pre.right != null) {
+                    pre = pre.right;
+                }
+                pre.right = root.right;
+                root.right = root.left;
+                root.left = null;
+            } else {
+                list.add(root.val);
+            }
+            if (root.right != null) {
+                queue.offer(root.right);
+            }
+        }
+        return list;
+    }
+}
diff --git a/leetcode_Java/Solution0144.java b/leetcode_Java/Solution0144.java
@@ -171,4 +171,38 @@ public List<Integer> preorderTraversal(TreeNode root) {
         }
         return resList;
     }
+}
+
+
+/*
+ * 迭代思路：
+ * 1、简单理解：把左子树塞到根节点和右节点中间，每个节点都要做同样的操作
+ * 2、节点连接步骤：
+ *    1）前序遍历是中左右，即根节点→左子树→右子树
+ *    2）左子树遍历的最后一个节点是 左子树的最后一个右子节点，因此要将其连接到根节点的右节点上
+ *    3）根节点的右指针要指向左节点，左指针指向空，从而形成中左右的链表
+ * 2、遍历逻辑：
+ *    1）根指针的移动代表着前序遍历的顺序，循环遍历条件是根指针不为空
+ *    2）如果根节点的左节点不为空，则进行节点连接步骤；如果为空，则将节点值存入列表，根指针指向右节点
+ * 3、“114.二叉树展开为链表”的解法
+ * */
+class Solution {
+    public List<Integer> flatten(TreeNode root) {
+        List<Integer> list = new ArrayList<>();
+        while (root != null) {
+            if (root.left != null) {
+                TreeNode temp = root.left;
+                while (temp.right != null) {
+                    temp = temp.right;
+                }
+                temp.right = root.right;
+                root.right = root.left;
+                root.left = null;
+            } else {
+                list.add(root.val);
+                root = root.right;
+            }
+        }
+        return list;
+    }
 }
