day20-二叉树part07

class Solution {private List<Integer> list = new ArrayList<>();private void traversal(TreeNode root) {if (root == null) return;traversal(root.left);list.add(root.val); // 将二叉搜索树转换为有序数组traversal(root.right);}public int getMinimumDifference(TreeNode root) {list.clear();traversal(root);if (list.size() < 2) return 0;int result = Integer.MAX_VALUE;for (int i = 1; i < list.size(); i++) { // 统计有序数组的最小差值result = Math.min(result, list.get(i) - list.get(i - 1));}return result;}
}

class Solution {int marg = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {if (root == null) {return 0;}getMinimumDifference(root.left);if (pre != null) {marg = Math.min(marg, root.val - pre.val);}pre = root;getMinimumDifference(root.right);return marg;}
}

540.有序数组的单一元素 

        思路1：使用map计数

class Solution {public int singleNonDuplicate(int[] nums) {Map<Integer,Integer> map = new HashMap<>();for(int num : nums){if(map.containsKey(num)){map.put(num,map.get(num) + 1);}else{map.put(num,1);}}for(int key : map.keySet()){if(map.get(key) == 1){return key;}}return 0;}
}

        思路2：遍历数组异或

class Solution {public int singleNonDuplicate(int[] nums) {int ans = 0;for(int x : nums){ans = ans^x;}return ans;}
}

class Solution {public int singleNonDuplicate(int[] nums) {int left = 0;int right = nums.length - 1;while(right > left){int mid = (right - left) / 2 + left;//mid为偶数 mid^1为mid+1//mid为奇数 mid^1为mid-1if(nums[mid] == nums[mid^1]){left = mid + 1;}else{right = mid;}}return nums[left];}
}

class Solution {public int[] findMode(TreeNode root) {List<Integer> res = new ArrayList<>();findMode1(root,res);Map<Integer,Integer> map = new HashMap<>();for(int num : res){if(map.containsKey(num)){map.put(num,map.get(num) + 1);}else{map.put(num,1);}}int maxCount = 0;for(int count : map.values()){maxCount = Math.max(maxCount,count);}List<Integer> modes = new ArrayList<>();for(int num : map.keySet()){if(map.get(num) == maxCount){modes.add(num);}}int[] ressult = new int[modes.size()];for(int i = 0;i < modes.size();i++){ressult[i] = modes.get(i);}return ressult;}private void findMode1(TreeNode root,List<Integer> res){if(root == null){return;}findMode1(root.left,res);res.add(root.val);findMode1(root.right,res);}
}

class Solution {ArrayList<Integer> resList = new ArrayList<>();int maxValue = 0;int count = 0;TreeNode pre = null;public int[] findMode(TreeNode root) {findMode1(root);int[] res = new int[resList.size()];for(int i = 0;i < resList.size(); i++){res[i] = resList.get(i);}return res;}private void findMode1(TreeNode root){if(root == null){return;}findMode1(root.left);if(pre == null){count = 1;}else if(pre.val == root.val){count++;}else{count = 1;}if(count == maxValue){resList.add(root.val);}if(count > maxValue){maxValue = count;resList.clear();resList.add(root.val);}pre = root;findMode1(root.right);}
}

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//先看根节点是不是祖先if(root == null || root == p || root == q){return root;}//如果根节点是祖先，有没有更近的祖先呢//后序遍历 左右中往上返回TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);//如果有的话显然只能在一侧 不然就是根节点最近if(left == null){return right;}if(right == null){return left;}//如果没有更近的，默认还是返回rootreturn root;}
}