手机看黄山网站网页制作教程视频
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;}}}