巢湖seo推广,优化网站除了百度站长,用dw如何做网站,京津冀网站建设公司输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true#xff0c;否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树#xff1a; 5 / \ 2 6 / \ 1 3 示例 1#xff1a;
输入: [1,6,…输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树 5 / \ 2 6 / \ 1 3 示例 1
输入: [1,6,3,2,5] 输出: false 示例 2
输入: [1,3,2,6,5] 输出: true
提示
数组长度 1000
思路找到第一个比根大的数字xx右边所有数字都要比根大才符合定义。
然后对左右子树重复上述过程。
class Solution {int[] postorder;public boolean verifyPostorder(int[] postorder) {this.postorderpostorder;return verify(0, postorder.length - 1); }// 递归实现private boolean verify(int left, int right){if (left right) return true;int rootValue postorder[right]; // 当前根// 找出第一个大于根节点的右边必须都在右子树中int k left;while (k right postorder[k] rootValue){ k;}//判断for (int i k; i right; i){if (postorder[i] rootValue) return false;}return verify(left, k - 1) verify(k, right - 1);}
} 输入一棵二叉树和一个整数打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树以及目标和 sum 22 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回:
[ [5,4,11,2], [5,8,4,5] ]
提示
节点总数 10000
思路深搜回溯
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {ListListInteger ansnew ArrayList();ListInteger tempnew ArrayList();public ListListInteger pathSum(TreeNode root, int sum) {help(root,sum);return ans;}public void help(TreeNode root, int sum){if(rootnull)return;temp.add(root.val);sum-root.val;if(sum0 root.leftnull root.rightnull){ans.add(new ArrayList(temp));}help(root.left,sum);help(root.right,sum);temp.remove(temp.size() - 1);}
} 请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。
示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2 输入head [[1,1],[2,1]] 输出[[1,1],[2,1]] 示例 3 输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]] 示例 4
输入head [] 输出[] 解释给定的链表为空空指针因此返回 null。
提示
-10000 Node.val 10000 Node.random 为空null或指向链表中的节点。 节点数目不超过 1000 。
思路先把每个节点后面复制一个相同的节点为了方便处理好random。然后再分开即可。
空间O(1)
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;}
}
*/
class Solution {public Node copyRandomList(Node head) {if (head null) {return head;}//将拷贝节点放到原节点后面例如1-2-3这样的链表就变成了这样1-1-2-3-3for (Node node head, copy null; node ! null; node node.next.next) {copy new Node(node.val);copy.next node.next;node.next copy;}//把拷贝节点的random指针安排上for (Node node head; node ! null; node node.next.next) {if (node.random ! null) {node.next.random node.random.next;}}//分离拷贝节点和原节点变成1-2-3和1-2-3两个链表后者就是答案Node newHead head.next;for (Node node head, temp null; node ! null node.next ! null;) {temp node.next;node.next temp.next;node temp;}return newHead;}
} 序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树 1 / \ 2 3 / \ 4 5
序列化为 [1,2,3,null,null,4,5] 提示: 这与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态你的序列化和反序列化算法应该是无状态的。
思路我们普通的遍历前序中序后序序列通常是不能唯一确定一个二叉树的需要前中结合或者后中结合。是因为我们不知道哪里可以停止比如例子中到3时我们不知道该挂到2的下面还是2两边都是null3应该挂1的右边。解决方法就是把所有的null记录下来比如例子中的二叉树前序12nullnull34nullnull5nullnull。下面是在这种做法的实现。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
public class Codec {public String serialize(TreeNode root) { //用StringBuilderreturn ser_help(root, new StringBuilder()).toString();}public StringBuilder ser_help(TreeNode root, StringBuilder str){if(null root){str.append(null,);return str;}str.append(root.val); str.append(,);str ser_help(root.left, str);str ser_help(root.right, str);return str;}public TreeNode deserialize(String data) {ListString list_word new LinkedListString(Arrays.asList(data.split(,)));return deser_help(list_word);}public TreeNode deser_help(ListString li){if(li.get(0).equals(null)){li.remove(0);return null;}TreeNode res new TreeNode(Integer.valueOf(li.get(0)));li.remove(0);res.left deser_help(li);res.right deser_help(li);return res;}
}// Your Codec object will be instantiated and called as such:
// Codec codec new Codec();
// codec.deserialize(codec.serialize(root));
