三门峡市建设局网站,信用网站建设,建设网站要什么手续,北京好的做网站的公司哪家好一、LeetCode 530 二叉搜索树的最小绝对值
题目链接#xff1a;530.二叉搜索树的最小绝对值https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 思路一#xff1a;利用搜索二叉树的中序遍历结果为有序数组的性质#xff0c;将遍历结果保存到数组中#xf…一、LeetCode 530 二叉搜索树的最小绝对值
题目链接530.二叉搜索树的最小绝对值https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 思路一利用搜索二叉树的中序遍历结果为有序数组的性质将遍历结果保存到数组中再找最小绝对值。 class Solution {ListInteger 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 {ListInteger 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;* }* }*/
三、LeetCode 236 二叉树的最近公共祖先
题目链接236.二叉树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/明日待续......
