【LeetCode-中等题】114. 二叉树展开为链表

题目

方法一：前序遍历（构造集合） + 集合（构造新树）

 List<TreeNode> res = new ArrayList<>();public void flatten(TreeNode root) {dfs(root);for(int i  = 0 ; i <res.size() ; i++){if(i == res.size()-1){//处理最后一个节点res.get(i).left = null;res.get(i).right = null;break;}res.get(i).left = null;res.get(i).right = res.get(i+1);}}//前序遍历public void dfs(TreeNode root) {if(root == null ) return ;res.add(root);dfs(root.left);dfs(root.right);}

方法二：原地构建

1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

public void flatten(TreeNode root) {while(root !=null){//左子树为 null，直接考虑下一个节点if (root.left == null) {root = root.right;} else {// 找左子树最右边的节点TreeNode  pre = root.left;while(pre.right !=null){pre =pre.right;}//将原来的右子树接到左子树的最右边节点pre.right = root.right;// 将左子树插入到右子树的地方root.right = root.left;root.left = null;// 考虑下一个节点root = root.right;}}}

方法三：前序遍历–迭代（构造集合） + 集合（构造新树）

 public void flatten(TreeNode root) {List<TreeNode> res = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();while(!stack.isEmpty() || root != null){while(root != null) {res.add(root);stack.push(root);root = root.left;}root = stack.pop();root = root.right;}for(int i  = 0 ; i <res.size() ; i++){if(i == res.size()-1){//处理最后一个节点res.get(i).left = null;res.get(i).right = null;break;}res.get(i).left = null;res.get(i).right = res.get(i+1);}}