代码随想录算法训练营 DAY20

代码随想录算法训练营 DAY20 | 二叉树(7)

一、LeetCode 530 二叉搜索树的最小绝对值

题目链接：530.二叉搜索树的最小绝对值https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

思路一：利用搜索二叉树的中序遍历结果为有序数组的性质，将遍历结果保存到数组中，再找最小绝对值。

class Solution {List<Integer> list = new LinkedList<>();public int getMinimumDifference(TreeNode root) {//二叉搜索树的中序遍历结果是一个有序数组midgo(root);int ans = Integer.MAX_VALUE;for(int i = 1; i < list.size(); i++){int temp = list.get(i) - list.get(i-1);if( temp < ans){ans = temp;}}return ans;}public void midgo(TreeNode root){if(root == null){return;}midgo(root.left);list.add(root.val);midgo(root.right);}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

思路二：利用pre节点记录上个遍历到的节点数值，直接完成递归遍历和计算。

class Solution {int result = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {travel(root);return result;}public void travel(TreeNode root){if(root == null){return;}travel(root.left);//前一个节点不为空，比较差值与已保存的最小绝对值if(pre != null){result = Math.min(result,root.val-pre.val);}//记录前一个节点pre = root;travel(root.right);}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

二、LeetCode 501 二叉搜索树中的众数

题目链接：501.二叉搜索树中的众数https://leetcode.cn/problems/find-mode-in-binary-search-tree/

思路：利用二叉搜索树中序遍历为有序数组的性质，设置pre记录上一个节点，对众数进行计数及结果更新。

 //二叉搜索树特性：中序遍历结果为有序数组
class Solution {List<Integer> list;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {list = new ArrayList<>();maxCount = 0;count = 0;pre = null;travel(root);int n = list.size();int[] ans = new int[n];for(int i = 0; i < n; i++){ans[i] = list.get(i);}return ans;}public void travel(TreeNode root){if(root == null){return;}travel(root.left);//利用中序遍历特性计数if(pre == null || root.val != pre.val){count = 1;}else{count++;}//更新结果及maxCountif(count > maxCount){maxCount = count;//最大值改变，清空结果list.clear();list.add(root.val);}else if(count == maxCount){//最大值未变，添加结果list.add(root.val);}pre = root;travel(root.right);}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/