530.二叉搜索树的最小绝对差
题目链接:530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)
思路
题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树,二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊,差值之类的,就把它想成在一个有序数组上求最值,求差值,这样就简单多了。
方法一:可以把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了。
方法二:双指针,用一个 pre 节点记录一下 cur 节点的前一个节点。然后求差值即可通过一次遍历直接得到结果。
代码
1 class Solution { 2 TreeNode pre;// 记录上一个遍历的结点 3 int result = Integer.MAX_VALUE; 4 public int getMinimumDifference(TreeNode root) { 5 if(root==null)return 0; 6 traversal(root); 7 return result; 8 } 9 public void traversal(TreeNode root){ 10 if(root==null)return; 11 //左 12 traversal(root.left); 13 //中 14 if(pre!=null){ 15 result = Math.min(result,root.val-pre.val); 16 } 17 pre = root; 18 //右 19 traversal(root.right); 20 } 21 }
1 // 迭代法-中序遍历 2 class Solution { 3 TreeNode pre; 4 Stack<TreeNode> stack; 5 public int getMinimumDifference(TreeNode root) { 6 if (root == null) return 0; 7 stack = new Stack<>(); 8 TreeNode cur = root; 9 int result = Integer.MAX_VALUE; 10 while (cur != null || !stack.isEmpty()) { 11 if (cur != null) { 12 stack.push(cur); // 将访问的节点放进栈 13 cur = cur.left; // 左 14 }else { 15 cur = stack.pop(); 16 if (pre != null) { // 中 17 result = Math.min(result, cur.val - pre.val); 18 } 19 pre = cur; 20 cur = cur.right; // 右 21 } 22 } 23 return result; 24 } 25 }
总结
遇到在二叉搜索树上求什么最值,求差值之类的,都要思考一下二叉搜索树可是有序的,要利用好这一特点。
同时要学会在递归遍历的过程中如何记录前后两个指针,这也是一个小技巧,学会了还是很受用的。
501.二叉搜索树中的众数
题目链接:501. 二叉搜索树中的众数 - 力扣(LeetCode)
思路
使用pre指针和cur指针的技巧,步骤如下。
- pre=null时,cur遍历到了左子树的叶子结点,此时cur所出现的次数为1
- 若pre.val=cur.val时,证明前向结点值后向结点值相等,即cur所出现次数+1
- 否则pre.val!=cur.val,证明前向结点值和后向结点值不等,即cur出现1次
- 判断该结点所出现的次数是否等于maxCount,是的话就加入list
- 若不是则更新maxCount,以及更新list
代码
// 中序遍历-不使用额外空间,利用二叉搜索树特性 class Solution { ArrayList<Integer> resList; int maxCount; int count; TreeNode pre; public int[] findMode(TreeNode root) { resList = new ArrayList<>(); maxCount = 0; count = 0; pre = null; findMode1(root); int[] res = new int[resList.size()]; for (int i = 0; i < resList.size(); i++) { res[i] = resList.get(i); } return res; } public void findMode1(TreeNode root) { if (root == null) { return; } findMode1(root.left); int rootValue = root.val; // 计数 if (pre == null || rootValue != pre.val) { count = 1; } else { count++; } // 更新结果以及maxCount if (count > maxCount) { resList.clear(); resList.add(rootValue); maxCount = count; } else if (count == maxCount) { resList.add(rootValue); } pre = root; findMode1(root.right); } }
// 迭代法 class Solution { public int[] findMode(TreeNode root) { TreeNode pre = null; Stack<TreeNode> stack = new Stack<>(); List<Integer> result = new ArrayList<>(); int maxCount = 0; int count = 0; TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur =cur.left; }else { cur = stack.pop(); // 计数 if (pre == null || cur.val != pre.val) { count = 1; }else { count++; } // 更新结果 if (count > maxCount) { maxCount = count; result.clear(); result.add(cur.val); }else if (count == maxCount) { result.add(cur.val); } pre = cur; cur = cur.right; } } return result.stream().mapToInt(Integer::intValue).toArray(); } }
扩展
如果本题不是二叉搜索数,那可采用暴力法,把这个树都遍历了,用map统计频率,把频率排个序,最后取前面高频的元素的集合。
使用暴力法时,注意以下细节。
- 用前中后序哪种遍历也不重要,因为就是要全遍历一遍,怎么个遍历法都行,层序遍历都没毛病!
- 要把map转化数组即
List<Map.Entry<Integer, Integer>>,再进行排序。
代码
1 class Solution { 2 public int[] findMode(TreeNode root) { 3 Map<Integer, Integer> map = new HashMap<>(); 4 List<Integer> list = new ArrayList<>(); 5 if (root == null) return list.stream().mapToInt(Integer::intValue).toArray(); 6 // 获得频率 Map 7 searchBST(root, map); 8 List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream() 9 .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue())) 10 .collect(Collectors.toList()); 11 list.add(mapList.get(0).getKey()); 12 // 把频率最高的加入 list 13 for (int i = 1; i < mapList.size(); i++) { 14 if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) { 15 list.add(mapList.get(i).getKey()); 16 } else { 17 break; 18 } 19 } 20 return list.stream().mapToInt(Integer::intValue).toArray(); 21 } 22 23 void searchBST(TreeNode curr, Map<Integer, Integer> map) { 24 if (curr == null) return; 25 map.put(curr.val, map.getOrDefault(curr.val, 0) + 1); 26 searchBST(curr.left, map); 27 searchBST(curr.right, map); 28 } 29 30 }
236. 二叉树的最近公共祖先
题目链接:236. 二叉树的最近公共祖先 - 力扣(LeetCode)
思路
遇到这个题目首先想的是要是能自底向上查找就好了,这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢?
回溯啊,二叉树回溯的过程就是从低到上。
后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
情况一:如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。
判断逻辑是 如果递归遍历遇到q,就将q返回,遇到p 就将p返回,那么如果 左右子树的返回值都不为空,说明此时的中节点,一定是q 和p 的最近祖先。
情况二,就是节点本身p(q),它拥有一个子孙节点q(p)。其实情况一 和 情况二 代码实现过程都是一样的,也可以说,实现情况一的逻辑,顺便包含了情况二。
因为遇到 q 或者 p 就返回,这样也包含了 q 或者 p 本身就是 公共祖先的情况。
代码
1 class Solution { 2 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 3 if (root == null || root == p || root == q) { // 递归结束条件 4 return root; 5 } 6 7 // 后序遍历 8 TreeNode left = lowestCommonAncestor(root.left, p, q); 9 TreeNode right = lowestCommonAncestor(root.right, p, q); 10 11 if(left == null && right == null) { // 若未找到节点 p 或 q 12 return null; 13 }else if(left == null && right != null) { // 若找到一个节点 14 return right; 15 }else if(left != null && right == null) { // 若找到一个节点 16 return left; 17 }else { // 若找到两个节点 18 return root; 19 } 20 } 21 }
总结
-
求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。
-
在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
-
要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。
可以说这里每一步,都是有难度的,都需要对二叉树,递归和回溯有一定的理解。
本题没有给出迭代法,因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。
标签:pre,遍历,TreeNode,cur,随想录,二叉,搜索,null,root From: https://www.cnblogs.com/xpp3/p/17146579.html