昆明网站开发培训机构,做计算机项目的网站,栾城seo整站排名,设计网站要多久114.二叉树展开为链表 方法一#xff1a;对二叉树进行先序遍历#xff0c;得到各个节点被访问到的顺序#xff0c;利用数组存储下来#xff0c;然后在先序遍历之后更新每个节点的左右节点的信息#xff0c;将二叉树展开为链表
/*** Definition for a binary tree node.* …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) {ListTreeNode list new ArrayListTreeNode();preorderTraversal(root,list);int size list.size();for(int i 1;isize;i){TreeNode prev list.get(i - 1),curr list.get(i);prev.left null;prev.right curr;}}public void preorderTraversal(TreeNode root, ListTreeNode 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;}}}
