【LeetCode热题100】--114.二叉树展开为链表

114.二叉树展开为链表

方法一：对二叉树进行先序遍历，得到各个节点被访问到的顺序，利用数组存储下来，然后在先序遍历之后更新每个节点的左右节点的信息，将二叉树展开为链表

/*** 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;*     }* }*/
class Solution {public void flatten(TreeNode root) {List<TreeNode> list = new ArrayList<TreeNode>();preorderTraversal(root,list);int size = list.size();for(int i =  1;i<size;i++){TreeNode prev = list.get(i - 1),curr = list.get(i);prev.left = null;prev.right = curr;}}public void preorderTraversal(TreeNode root, List<TreeNode> list) {if (root != null) {list.add(root);preorderTraversal(root.left, list);preorderTraversal(root.right, list);}}}

方法二：

/*** 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;*     }* }*/
class Solution {public void flatten(TreeNode root) {if (root == null) {return;}// 1. 先将左子树展开为链表flatten(root.left);// 2. 将右子树展开为链表flatten(root.right);// 将左子树迁移到右子树中TreeNode node = root.left;if (node != null) {     // 如果左子树不为空// 3.1. 先找到左子树链表中的最右端的结点while (node.right != null) {node = node.right;}// 3.2. 将右子树插入到左子树的尾部结点node.right = root.right;// 3.3 将左子树换到右结点root.right = root.left;root.left = null;}}}