题1:
JZ68 二叉搜索树的最近公共祖先
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值 3.所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。 数据范围: 3<=节点总数<=10000 0<=节点值<=10000 如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5},如下图:1 import java.util.*; 2 3 /* 4 * public class TreeNode { 5 * int val = 0; 6 * TreeNode left = null; 7 * TreeNode right = null; 8 * public TreeNode(int val) { 9 * this.val = val; 10 * } 11 * } 12 */ 13 14 public class Solution { 15 /** 16 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 17 * 18 * 19 * @param root TreeNode类 20 * @param p int整型 21 * @param q int整型 22 * @return int整型 23 */ 24 Map<Integer,Integer> map; 25 public int lowestCommonAncestor (TreeNode root, int p, int q) { 26 // write code here 27 map=new HashMap<>(); 28 dfs(root); 29 Set<Integer> set=new HashSet<>(); 30 set.add(p); 31 while (map.containsKey(p)){ 32 set.add(map.get(p)); 33 p=map.get(p); 34 } 35 while (!set.contains(q)) { 36 q=map.get(q); 37 } 38 return q; 39 } 40 41 public void dfs(TreeNode root) { 42 if (root==null) return; 43 if (root.left!=null){ 44 map.put(root.left.val,root.val); 45 dfs(root.left); 46 } 47 if (root.right!=null){ 48 map.put(root.right.val,root.val); 49 dfs(root.right); 50 } 51 } 52 }
思路:用最普通的树解决。
题2:
JZ9 用两个栈实现队列
描述
用两个栈来实现一个队列,使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。 数据范围: n\le1000n≤1000 要求:存储n个元素的空间复杂度为 O(n)O(n) ,插入与删除的时间复杂度都是 O(1)O(1)1 import java.util.Stack; 2 3 public class Solution { 4 Stack<Integer> stack1 = new Stack<Integer>(); 5 Stack<Integer> stack2 = new Stack<Integer>(); 6 7 public void push(int node) { 8 stack1.push(node); 9 } 10 11 public int pop() { 12 if (stack2.isEmpty()) { 13 while (!stack1.isEmpty()) stack2.push(stack1.pop()); 14 } 15 return stack2.pop(); 16 } 17 }
思路:将第一个栈全部弹出,顺序就反过来了