网站置顶jq,网站域名更改后怎么做映射,政协网站信息化建设的作用,招聘做网站二叉树结构转化
通常将二叉树根据某些要求进行结构重构#xff0c;比如线性结构转化(链表#xff0c;数组)#xff0c;序列化等。
常见题型 注#xff1a;这类题目最基本的解题思路是利用递归分治 (也可以使用迭代方法)#xff0c;在构建树结构的时候#xff0c;我们通…二叉树结构转化
通常将二叉树根据某些要求进行结构重构比如线性结构转化(链表数组)序列化等。
常见题型 注这类题目最基本的解题思路是利用递归分治 (也可以使用迭代方法)在构建树结构的时候我们通常会使用前序遍历的思路自上而下进行建树每一次递归中得到左右子树的值进行连接。 链表类
Leetcode 114 - Flatten Binary Tree to LinkedList
LeetCode 426 - Convert BST to Sorted Doubly Linked List
线性数组或字符类
Leetcode 297. 序列化和反序列化二叉树
Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal
Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
Leetcode 536. Construct Binary Tree from String
Leetcode 606. Construct String from Binary Tree
Leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal
二叉搜索树
Leetcode 449. Serialize and Deserialize BST 题目思路
Leetcode 114 - Flatten Binary Tree to LinkedList
将二叉树以前序遍历的顺序转化成连接结构要求in-place即不占用额外空间存储新的链表结构。基本思路是递归分治这里我们使用后序遍历的思路先拿到左右结点然后转化成链表结构在每一次递归中
拿到左右子结点如果左子树为空则直接返回右子树如果左子树不为空将左子树的最右边的结点与当前节点右子树连接然后将当前节点右边连接到该左子树然后将当前节点左子树置空。 代码如下
class Solution {public void flatten(TreeNode root) {dfs(root);}private void dfs(TreeNode root) {if (rootnull) return;if (root.leftnull root.rightnull) return;dfs(root.left);dfs(root.right);if (root.leftnull) return;else {TreeNode dum root.left;while (dum.right!null) {dum dum.right;}dum.right root.right;root.right root.left;root.left null;}}
} Leetcode 606. Construct String from Binary Tree 二叉树序列化问题根据二叉树前序遍历顺序将各节点按照继承关系打印出来 例子[1,2,3,4] - 1(2(4))(3) 二叉树序列化通常思路就是前序遍历依次打印各个节点按照分治的思路我们在每一次递归任务中需要做以下步骤
打印当前节点打印左括号遍历左子树打印右括号判断右子树是否为空如果不为空重复 23(打印右子树)4。
代码如下
时间复杂度 ; 空间复杂度 , h代表递归深度。
class Solution {StringBuilder str new StringBuilder();public String tree2str(TreeNode root) {dfs(root);return str.toString();}private void dfs(TreeNode root) {if (rootnull) return;str.append(root.val);if (root.leftnull root.rightnull) return;str.append(();dfs(root.left);str.append());// skip if right nullif (root.right!null) {str.append(();dfs(root.right);str.append());}}
} Leetcode 536. Construct Binary Tree from String
这道题目则是上面LC.606的反序列化通过给定序列化字符串构造原始的树结构由于序列化后可以通过() 来判断节点的父子关系这道题思路有一些类似Leetcode基础计算器或者表达式计算的问题我们需要维护一个栈结构在遍历字符串过程中
如果遇到左括号继续循环如果遇到数字或者负号读取数字位创建结点并加入Stack中如果遇到右括号即需要开始处理结点父子关系将最近结点pop出来pop后栈中最顶上的结点一定是pop出结点的父亲结点将当前节点连接到该父亲结点上左优先如果左边不为空则连接到右子树。
代码如下
时间复杂度 ; 空间复杂度 , h代表递归深度。
class Solution {public TreeNode str2tree(String s) {if (snull || s.length()0) return null;StackTreeNode stk new Stack();for (int i0; is.length();) {if (s.charAt(i)() {i;continue;} else if (s.charAt(i))) {if (!stk.isEmpty()) {TreeNode node stk.pop();TreeNode parent stk.peek();if (parent.leftnull) parent.left node;else parent.right node;}i;} else {String num ;while (is.length() ((s.charAt(i)0 s.charAt(i)9) || s.charAt(i)-)) {nums.charAt(i);i;}TreeNode node new TreeNode(Integer.parseInt(num));stk.push(node);}}return stk.pop();}
} Leetcode 297. 序列化和反序列化二叉树
上面两道题目的合并版比起使用上述括号形式进行序列化编码这道题目我们可以对于序列化的格式进行简化对于缺失的左右叶子结点我们用NULL来表示每一个结点以逗号隔开。
对于反序列化的步骤由于序列化是以前序遍历的顺序所以反序列化也利用前序遍历的顺序每一次递归过程中进行如下操作
根据当前遍历的结点创建二叉树结点并从列表中移除该结点向下遍历左右子树得到左右子树将当前节点连接到左右子树并返回当前节点 前序遍历的特性是根-左-右是比较适合构建二叉树这类问题 代码如下
public class Codec {StringBuilder str;// Encodes a tree to a single string.public String serialize(TreeNode root) {str new StringBuilder();helper(root);return str.toString().substring(0, str.length()-1);}private void helper(TreeNode root) {if (rootnull) {str.append(null,);return;}str.append(root.val,);helper(root.left);helper(root.right);}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {ListString nodes new LinkedListString(Arrays.asList(data.split(,)));return deshelper(nodes);}private TreeNode deshelper(ListString nodes) {if (nodesnull || nodes.size()0) return null;if (nodes.get(0).equals(null)) {nodes.remove(0);return null;}TreeNode curr new TreeNode(Integer.parseInt(nodes.get(0)));nodes.remove(0);curr.left deshelper(nodes);curr.right deshelper(nodes);return curr;}
}
