南昌做个网站多少钱,wordpress4.x,开源公司网站,广州海珠网站建设Problem: 114. 二叉树展开为链表 文章目录 题目描述思路解题方法复杂度Code 题目描述
给你二叉树的根结点 root #xff0c;请你将它展开为一个单链表#xff1a; 1.展开后的单链表应该同样使用 TreeNode #xff0c;其中 right 子指针指向链表中下一个结点#xff0c;而左… Problem: 114. 二叉树展开为链表 文章目录 题目描述思路解题方法复杂度Code 题目描述
给你二叉树的根结点 root 请你将它展开为一个单链表 1.展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。 2/展开后的单链表应该与二叉树 先序遍历 顺序相同。 思路
我们易知树与链表两种数据结构都可以通过指针操作来实现换一句说两种数据结构都可以归结为一种链式数据结构只不过一般情况下一般普通链表每一个节点后都只有一个next指针一般的二叉树每个节点后都会有两个指针left指针和right指针所以我们即可想到使用一个树来模拟实现链表 1.创建虚拟头节点和尾指针尾指针初始化指向虚拟头节点。 2.每次遍历过程中将上一节点的right指针指向当前节点上一节点的left指针置为null 解题方法 1.创建虚拟头节点和尾指针尾指针初始化指向虚拟头节点。 2.编写辅助的前序遍历函数每次先取出当前节点的左右子树再将每次按先序遍历的到的节点添加到尾指针后 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code
/*** 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 {//创建虚拟头节点private TreeNode dummyHead new TreeNode();//创建尾指针private TreeNode tail dummyHead;/*** 将一个二叉树展开为一个单链表** param root 树的根节点*/public void flatten(TreeNode root) {preOrder(root);}/*** 先序遍历将每次遍历到的节点添加到链表中** param root 树的根节点*/private void preOrder(TreeNode root) {if (root null) {return;}//先取出当前节点的左右节点TreeNode leftNode root.left;TreeNode rightNode root.right;//把遍历到的节点放在链表中tail.right root;tail root;tail.left null;preOrder(leftNode);preOrder(rightNode);}}
