2025年- H52-Lc160--114. 二叉树展开为链表(前序遍历 + 用栈 + 原地修改）--Java版

1.题目描述

2.思路

（1）使用前序遍历 + 重构指针
（2）前序遍历 + 用栈
//实现前序遍历（根 -> 左 -> 右），你需要先压右子树，再压左子树，因为栈是**后进先出（LIFO）**的结构：

3.代码实现

方法一：前序遍历 + 重构指针( no try）

 if (root == null) return;flatten(root.right);flatten(root.left);root.right = prev;root.left = null;prev = root;

方法二：前序遍历 + 用栈 （yes try）

import java.util.*;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 class H114 {public void flatten(TreeNode root) {List<Integer> reasult=new ArrayList<>();if (root==null) return;Stack<TreeNode> st=new Stack<>();st.push(root);while(!st.isEmpty()){TreeNode cur=st.pop();//实现前序遍历（根 -> 左 -> 右），你需要先压右子树，再压左子树，因为栈是**后进先出（LIFO）**的结构：if(cur.right!=null){st.push(cur.right);}if(cur.left!=null){st.push(cur.left);}// 改指针if(!st.isEmpty()){cur.right=st.peek();}cur.left=null;}}
}