赞
踩
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
示例 2:
提示:
树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105
因为是二叉搜索树,所以用中序遍历得出一个有序数组然后直接算差就可以
class Solution { TreeNode pre; int result = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { if(root==null)return 0; traversal(root); return result; } public void traversal(TreeNode root){ if(root==null)return; traversal(root.left); if(pre!=null){ result = Math.min(result,root.val-pre.val); } pre = root; traversal(root.right); } }
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
示例 1:
示例 2:
提示:
因为是二叉搜索树,所以中序遍历得到有序数组,然后统计出现频率就可以了
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++; } if (count > maxCount) { resList.clear(); resList.add(rootValue); maxCount = count; } else if (count == maxCount) { resList.add(rootValue); } pre = root; findMode1(root.right); } }
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
示例 2:
示例 3:
提示:
回溯可以自底向上查,方便找公共祖先,所以用后序来做
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 && right == null) { return null; }else if(left == null && right != null) { return right; }else if(left != null && right == null) { return left; }else { return root; } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。