[高频] 四.基础算法和数据结构II

662. Guess Number Game：点击打开链接

/* The guess API is defined in the parent class GuessGame. @param num, your guess @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); */ public class Solution extends GuessGame { /** * @param n an integer * @return the number you guess */ public int guessNumber(int n) { int start=1; int end=n; while(start+1<end){ int mid=start+(end-start)/2; if(guess(mid)==0){ return mid; }else if(guess(mid)==-1){ //my number is lower than your guess end=mid; }else if(guess(mid)==1){ start=mid; } } if(guess(start)==0){ return start; } return end; } }

61. Search for a Range：点击打开链接

思路：二分法，先找start点，再找end点

public class Solution { /** *@param A : an integer sorted array *@param target : an integer to be inserted *return : a list of length 2, [index1, index2] */ public int[] searchRange(int[] A, int target) { if(A.length==0) { return new int[]{-1,-1}; } int[] result=new int[2]; int start=0,end=A.length-1; //找start点 while(start+1<end){ int mid=start+(end-start)/2; if(A[mid]==target){ //因为找start点，在左边界，找到target后继续向左边界找 end=mid; }else if(A[mid]<target){ start=mid; }else{ end=mid; } } if(A[start]==target){ //因为是要找start点，因此要先写start，尽量从start方向找到 result[0]=start; }else if(A[end]==target){ result[0]=end; }else{ result[0]=result[1]=-1; return result; } start=0; //找end点 end=A.length-1; while(start+1<end){ int mid=start+(end-start)/2; if(A[mid]==target){ //因为找end点，在右边界，找到target后继续向右边界找 start=mid; }else if(A[mid]<target){ start=mid; }else{ end=mid; } } if(A[end]==target){ //因为是要找end点，因此要先写end，尽量从end方向找到 result[1]=end; }else if(A[start]==target){ result[1]=start; }else{ result[0]=result[1]=-1; return result; } return result; } }

661. Convert BST to Greater Tree：点击打开链接

思路：BST的中序遍历，节点访问顺序是从小到大的

         将中序遍历左根右的顺序你过来，变成右根左，节点访问顺序是从大到小的，这样就可以反向计算累加的和，并更新结点的值

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @return the new root */ public TreeNode convertBST(TreeNode root) { //non-recursion if(root==null){ return null; } Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; int sum=0; while(cur!=null || !stack.isEmpty()){ while(cur!=null){ stack.push(cur); cur=cur.right; } cur=stack.pop(); cur.val+=sum; //更新当前值 sum=cur.val; //更新sum cur=cur.left; } return root; } } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int sum=0; public TreeNode convertBST(TreeNode root) { //recursion helper(root); return root; } private void helper(TreeNode root){ if(root==null){ return; } helper(root.right); root.val+=sum; sum=root.val; helper(root.left); } }

448. Inorder Successor in Binary Search Tree：点击打开链接

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if(root==null || p==null){ return null; } if(root.val<=p.val){ return inorderSuccessor(root.right, p); }else{ TreeNode left=inorderSuccessor(root.left, p); return (left!=null)?left:root; } } }

650. Binary Tree Leaves Order Traversal：点击打开链接

1 1 2 1 1 / \ / \ 2 3 2 1 3 0 / \ / \ 4 5 4 5 0 Output：[[4,5,3],[2],[1]

思路：根据左右子树的相对位置，拿到每一个节点的高度，相同高度的节点值放同一个list

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root the root of binary tree * @return collect and remove all leaves */ List<List<Integer>> result=new ArrayList<>(); public List<List<Integer>> findLeaves(TreeNode root) { if(root==null){ return result; } getHeight(root); return result; } private int getHeight(TreeNode root){ int leftHeight=root.left!=null?getHeight(root.left)+1:0; //其实这样就是左右根的遍历，后序遍历 int rightHeight=root.right!=null?getHeight(root.right)+1:0; //而且根是上一层的，所有就能保证从左到右的顺序 int height=Math.max(leftHeight,rightHeight); if(result.size()<=height){ result.add(new ArrayList<Integer>()); } result.get(height).add(root.val); //倒着放，先放高度2，再放1，再放0 return height; //因为先拿到高度2，然后才是后面的高度 } }

651. Binary Tree Vetical Order Traversal：点击打开链接

思路：从根节点开始，给序号0，然后开始层序遍历，凡是左子节点序号减1，凡是右子节点序号加 1，这样就可以把相同列的节点值放在一起

         用map建立序号和所有与该序号对应的节点值

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ class Node{ TreeNode node; int pos; Node(TreeNode node,int pos){ this.node=node; this.pos=pos; } } public class Solution { /** * @param root the root of binary tree * @return the vertical order traversal */ public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> result=new ArrayList<>(); if(root==null){ return result; } Map<Integer,List<Integer>> map=new HashMap<>(); Queue<Node> queue=new LinkedList<>(); int maxVal=Integer.MIN_VALUE; //确定pos的左右边界 int minVal=Integer.MAX_VALUE; queue.offer(new Node(root,0)); while(!queue.isEmpty()){ Node cur=queue.poll(); minVal=Math.min(minVal,cur.pos); maxVal=Math.max(maxVal,cur.pos); if(!map.containsKey(cur.pos)){ List<Integer> list=new ArrayList<>(); list.add(cur.node.val); map.put(cur.pos,list); }else{ map.get(cur.pos).add(cur.node.val); } if(cur.node.left!=null){ queue.offer(new Node(cur.node.left,cur.pos-1)); } if(cur.node.right!=null){ queue.offer(new Node(cur.node.right,cur.pos+1)); } } for(int i=minVal;i<=maxVal;i++){ List<Integer> list=map.get(i); result.add(list); } return result; } }