109、二叉树展开为链表

题目描述：

非递归代码，其实也递归了：

class Solution { public void flatten(TreeNode root) { List<TreeNode> list = new ArrayList<>(); get(root,list); TreeNode pre = new TreeNode(-1); for (int i = 0; i < list.size(); i++) { if(i == 0){ list.get(i).left = null; pre = list.get(i); }else if (i == list.size() - 1) { pre.right = list.get(i); list.get(i).left = null; list.get(i).right = null; }else { pre.right = list.get(i); list.get(i).left = null; pre = list.get(i); } } } public void get(TreeNode node,List<TreeNode> list){ if(node == null){ return ; } list.add(node); get(node.left,list); get(node.right,list); } }

比较简单的写法

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