给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
【思路】
题目要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树,二叉搜索树是有序的。遇到在二叉搜索树上求最值、差值之类的,就把它想成在一个有序数组上求最值、差值,这样就简答多了。
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);
}
}
class Solution {
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
int result = Integer.MAX_VALUE;
if(root != null)
stack.add(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if(curr != null){
stack.pop();
if(curr.right != null)
stack.add(curr.right);
stack.add(curr);
stack.add(null);
if(curr.left != null)
stack.add(curr.left);
}else{
stack.pop();
TreeNode temp = stack.pop();
if(pre != null)
result = Math.min(result, temp.val - pre.val);
pre = temp;
}
}
return result;
}
}
标签:pre,26,二叉,搜索,result,null,root,stack
From: https://www.cnblogs.com/codingbao/p/17931499.html