【Hot100】LeetCode—114. 二叉树展开为链表

---

• 原题连接：114. 二叉树展开为链表

---

1- 思路

技巧——借助指针

思路：通过 ① 将左子树的右下结点的 .next ——> 拼接到当前节点的右子树上。

• 构造 cur 指针， cur = root
• 借助 pre 指针和 next 指针
  • pre 指针：用来定位左子树的最右下结点，用来拼接现有结点的右侧子树
  • next 指针：又来记录 cur.next 用来处理，用于 更新现有结点的右子树

---

• 1- 第一个 while 条件 **while(cur != null)**
  • 1.1 如果左侧不为 null
    • 定义 next ，记录翻转后的 next 结点，next = cur.left
    • 定义 pre，利用 while，定位 pre 到最右下结点pre = next
• 2- 更新逻辑
  • 2.1 利用 pre 定位到 左子树的 最右下结点
  • 2.2 pre的 next 为 cur.next
  • 2.3 cur.right = next
  • 2.4 cur.left = null;
• 3- 最终移动 cur
  • cur = cur.next

---

2- 实现

⭐114. 二叉树展开为链表——题解思路

class Solution {public void flatten(TreeNode root) {TreeNode cur = root;while(cur!=null){if(cur.left!=null){TreeNode next = cur.left;TreeNode pre = next;while(pre.right != null){pre = pre.right;}// 更新逻辑pre.right = cur.right;cur.right = next;cur.left = null;}cur = cur.right;}}
}

---

3- ACM 实现

public class falttern {public static 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;}}public static TreeNode build(String str){if(str == null || str.length()==0){return null;}String input = str.replace("[","");input = input.replace("]","");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for(int i = 0 ; i < parts.length;i++){if(!parts[i].equals("null")){nums[i] = Integer.parseInt(parts[i]);}else{nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while(!queue.isEmpty()&& index<parts.length){TreeNode node = queue.poll();if(index<nums.length && nums[index]!=null){node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if(index<nums.length && nums[index]!=null){node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}public static void flattern(TreeNode root){TreeNode cur = root;while(cur!=null){if(cur.left!=null){TreeNode pre = cur.left;TreeNode next = pre;while(pre.right!=null){pre = pre.right;}// 处理逻辑pre.right = cur.right;cur.right = next;cur.left = null;}cur = cur.right;}}static List<List<Integer>> res = new ArrayList<>();public static List<List<Integer>> levelOrder(TreeNode root) {if(root==null){return res;}
// 队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int len = queue.size();List<Integer> path = new ArrayList<>();while(len>0){TreeNode nowNode = queue.poll();path.add(nowNode.val);if(nowNode.left!=null) queue.offer(nowNode.left);if(nowNode.right!=null) queue.offer(nowNode.right);len--;}res.add(new ArrayList<>(path));}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);flattern(root);levelOrder(root);System.out.println("结果是"+res.toString());}
}