树系列问题II——二叉树

系列问题II——二叉树"/>

树系列问题II——二叉树

105. 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
解析过程：

/*** 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 {HashMap<Integer,Integer> hash=new HashMap<>();int[] pre;public TreeNode buildTree(int[] preorder, int[] inorder) {//将中序遍历中的元素加入hash表中for(int i=0;i<inorder.length;i++){hash.put(inorder[i],i);}pre=preorder;TreeNode root = BT(0,preorder.length-1,0,inorder.length-1);return root;}public TreeNode BT(int ps,int pe,int is,int ie){if(ps>pe || is>ie){return null;}//前序遍历中的第一个节点就是根节点int node=pre[ps];int value=hash.get(node);TreeNode root=new TreeNode(node);root.left=BT(ps+1,ps+value-is,is,value-1);root.right=BT(ps+value-is+1,pe,value+1,ie);return root;}
}

结果：
203 / 203 个通过测试用例
执行用时: 1 ms
内存消耗: 38.1 MB

106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。

例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7
解析过程：

/*** 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 {//因为从后序遍历中获取到根节点之后，需要在中序遍历中查找对应位置，然后分成左右子树，因此设置一个哈希表，用来存储中序遍历序列中的元素和索引的位置关系HashMap<Integer,Integer> hash=new HashMap<>();int[] Post;public TreeNode buildTree(int[] inorder, int[] postorder) {//将中序遍历中的值存入哈希表中for(int i=0;i<inorder.length;i++){hash.put(inorder[i],i);}Post=postorder;TreeNode root= BT(0,inorder.length-1,0,postorder.length-1);return root;}public TreeNode BT(int Is,int Ie,int Ps,int Pe){if(Is>Ie || Ps>Pe){return null;}//从后序遍历序列中得到根节点int node=Post[Pe];int value=hash.get(node);TreeNode root=new TreeNode(node);root.left=BT(Is,value-1,Ps,Ps+value-Is-1);root.right=BT(value+1,Ie,Ps+value-Is,Pe-1);return root;}
}

结果：
执行用时：1 ms, 在所有 Java 提交中击败了99.74%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了88.72%的用户
通过测试用例：202 / 202

100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
解析过程：

/*** 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 boolean isSameTree(TreeNode p, TreeNode q) {//两棵树相同   结构相同，并具有相同的值if(p==null && q==null){return true;}else if(p==null ||q==null){return false;}if(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

结果：
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.9 MB，在所有 Java 提交中击败了16.42%的用户
通过测试用例：60 / 60

116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
提示：
树中节点的数量少于 4096
-1000 <= node.val <= 1000

示例：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。
解析过程：

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {//层次遍历，每次遍历同一层if(root==null){return root;}//初始化队列Queue<Node> queue=new LinkedList<Node>();//将根节点（第一层节点）加入队列中queue.add(root);//若层数不为空while(!queue.isEmpty()){//记录当前队列大小int len=queue.size();for(int i=0;i<len;i++){//取出节点（先进先出）//remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。//poll():检索并删除此队列的头，如果此队列为空，则返回 null 。Node node=queue.poll();//peek():查看此队列顶部的对象，而不从队列中删除它。//element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。if(i<len-1){node.next=queue.peek();}//将下一层节点加入队列if(node.left!=null){queue.add(node.left);}if(node.right!=null){queue.add(node.right);}}}return root;  //返回根节点}
}

结果：
58 / 58 个通过测试用例
执行用时: 3 ms
内存消耗: 38.6 MB

117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），’#’ 表示每层的末尾。
解析过程：

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {//层次遍历Queue<Node> queue=new LinkedList<>();if(root == null){return root;}queue.offer(root);while(! queue.isEmpty()){int len=queue.size();for(int i=0;i<len;i++){Node node=queue.poll();if(i<len-1){node.next=queue.peek();}if(node.left !=null){queue.offer(node.left);}if(node.right !=null){queue.offer(node.right);}}}return root;}
}

结果：
执行用时：2 ms, 在所有 Java 提交中击败了31.38%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了65.57%的用户
通过测试用例：55 / 55

236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
解析过程：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//递归//1.如果root为p/q，且另一个节点在root的左子树或右子树中，则root为最近公共祖先//2.如果p和q在根节点的子树中，且分为两侧，则根节点为最近公共祖先/*3.递归左子树节点，返回LeftTree,递归右子树节点，返回RightTree1)若LeftTree和RightTree均为空，则返回null2）若LeftTree和RightTree均不为空，则root为最近公共祖先节点3）若LeftTree为空，RightTree不为空，返回RightTree4）若RightTree为空，LeftTree不为空，返回LeftTree*/if(root == null || root==p || root==q){return root;}TreeNode LeftTree=lowestCommonAncestor(root.left,p,q);TreeNode RightTree=lowestCommonAncestor(root.right,p,q);if(LeftTree == null && RightTree == null){return null;}//如果LeftTree为空，说明这两个节点在根结点的右子树上，返回右子树查找的结果if(LeftTree == null)  return RightTree;if(RightTree == null)  return LeftTree;return root;   //if(LeftTree != null && RightTree != null)}
}

结果：
执行用时：7 ms, 在所有 Java 提交中击败了56.78%的用户
内存消耗：40.7 MB, 在所有 Java 提交中击败了19.77%的用户
通过测试用例：31 / 31

297. 二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

解析过程：
方法一：先序遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {//先序遍历，若节点为空，则以"#!"结束if(root == null){return "#!";}String res=root.val+"!";res+=serialize(root.left);res+=serialize(root.right);return res;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {//将结果字符串变为字符串类型的数组，记为values,数组代表一棵二叉树先序遍历的节点顺序String[] values=data.split("!");Queue<String> queue=new LinkedList<>();for(int i=0;i<values.length;i++){queue.offer(values[i]);}return PreOrder(queue);}public TreeNode PreOrder(Queue<String> queue){//先序遍历的反序列化就是重做先序遍历，遇到“#”就生成null节点，结束生成后续子树的过程String value=queue.poll();if(value.equals("#")){return null;}TreeNode root=new TreeNode(Integer.valueOf(value));root.left=PreOrder(queue);root.right=PreOrder(queue);return root;}
}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

结果：
执行用时：16 ms, 在所有 Java 提交中击败了60.98%的用户
内存消耗：40 MB, 在所有 Java 提交中击败了86.34%的用户
通过测试用例：52 / 52

方法二：
层序遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {//层次遍历方法序列化//"!"表示一个值的结束if(root == null){return "#!";}String res=root.val+"!";Queue<TreeNode> queue=new LinkedList<>();queue.offer(root); while(! queue.isEmpty()){root=queue.poll();if(root.left !=null){res+=root.left.val+"!";queue.offer(root.left);}else {res+="#!";}if(root.right != null){res+=root.right.val+"!";queue.offer(root.right);}else{res+="#!";}}return res;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {//层次遍历反序列化与先序遍历方法一样，重做层遍历，遇到"#"就生成null节点，同时不把null节点放到队列里即可String[] values=data.split("!");int index=0;TreeNode root=generateNodeByString(values[index++]);Queue<TreeNode> queue=new LinkedList<>();if(root !=null){queue.offer(root);}TreeNode node=null;while(! queue.isEmpty()){node=queue.poll();node.left=generateNodeByString(values[index++]);node.right=generateNodeByString(values[index++]);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}}return root;}public TreeNode generateNodeByString(String val){if(val.equals("#") ){return null;}return new TreeNode(Integer.valueOf(val));}
}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

结果：
执行用时：72 ms, 在所有 Java 提交中击败了19.72%的用户
内存消耗：40.7 MB, 在所有 Java 提交中击败了48.65%的用户
通过测试用例：52 / 52

331. 验证二叉树的前序序列化
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

     _9_/   \3     2/ \   / \4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,3” 。

示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true

示例 2:
输入: “1,#”
输出: false

示例 3:
输入: “9,#,#,1”
输出: false
解析过程：

class Solution {public boolean isValidSerialization(String preorder) {return isValid(preorder);}public boolean isValid(String str){//先将字符串变成字符数组 String[] array=str.split(",");if(array[0].equals( "#") && array.length==1){return true;}if(array[0].equals("#") && array.length!=1){return false;}int count=1; //记录节点未知的叶节点的个数for(int i=0;i<array.length;i++){count--;if(count<0){return false;}else if(! array[i].equals("#")){//遇到非空节点，count+2count+=2;}}return count==0;}
}

结果：
执行用时：4 ms, 在所有 Java 提交中击败了58.41%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了46.71%的用户
通过测试用例：151 / 151

110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true
解析过程：

/*** 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 boolean isBalanced(TreeNode root) {//对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。//递归if(root == null){return true;}if(root.left ==null && root.right == null){return true;}return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left) &&  isBalanced(root.right);}//用于计算二叉树中的任意一个节点node的高度public int depth(TreeNode node){if(node==null){return 0;}else {return Math.max(depth(node.left),depth(node.right))+1;}}
}

结果：
执行用时：1 ms, 在所有 Java 提交中击败了70.66%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了54.42%的用户
通过测试用例：228 / 228

404. 左叶子之和
计算给定二叉树的所有左叶子之和。

示例：

   3/ \9  20/  \15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
解析过程：

/*** 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 int sumOfLeftLeaves(TreeNode root) {//递归，找到所有的左叶子，并相加if(root == null){return 0;}return DFS(root);}//首先保证是叶子节点public boolean leaf(TreeNode node){return (node.left==null)&&(node.right==null);}//然后计算所有左叶子之和public int DFS(TreeNode root){int sum=0;if(root.left !=null ){if(leaf(root.left)){sum+=root.left.val;}else{sum+=DFS(root.left);}}if(root.right!=null && !leaf(root.right)){sum+=DFS(root.right);}return sum;}
}

结果：
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.2 MB, 在所有 Java 提交中击败了36.28%的用户
通过测试用例：100 / 100