[LC]530题二叉搜索树的最小绝对差

①题目

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

示例 :

输入:

1
\
3
/
2

输出:
1

解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
注意: 树中至少有2个节点。

②思路

这个题我自己没做出来，所以看了别人的题解。

思路就是，使用中序遍历，在中序遍历的同时，计算差值。

③代码

 class Solution {

     TreeNode pre;

     int res = Integer.MAX_VALUE;       //res是一个全局变量，作为答案。它的具体计算，在helper函数里。

     public int getMinimumDifference(TreeNode root) {

         if(root==null)

             return 0;

         helper(root);

         return res;

     }

     private void helper(TreeNode root){

         if(root==null)  return;    //只是return（什么都不做了，跳出此轮的helper函数），而不要return一个数。

         helper(root.left);

         if(pre!=null)

             res = Math.min(res,Math.abs(root.val-pre.val));

         pre=root;

         helper(root.right);

     }

 }

 //中序遍历的结果是升序输出，所以在中序遍历的过程中，计算差值。

④学到的知识

1、中序遍历的核心代码部分就是，在递归时，先输出root.left.val，再输出root.val，最后输出root.right.val。

2、求两者中小的那个，就用Math.min(a,b)函数就行了，不要写什么if(a<b) return a;else return b;行数又多又不好看。

3、注意代码里的15行，也就是root什么时候传给pre。

4、从第10行到12行，就直接可以递归到该BST的左下角那个节点，

5、大概推一下BST左下角的递归流程：

马上要上课了，不跟这个旋转了90的图斗争了。

巴特西

[LC]530题二叉搜索树的最小绝对差

最新文章

热门文章

巴特西

[LC]530题 二叉搜索树的最小绝对差

最新文章

热门文章

[LC]530题二叉搜索树的最小绝对差