LeetCode 783号问题

来源:4-8 二分搜索树底层实现的顺序性 Contain Duplicate III

pfco

2019-09-20

private int res=Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
       minDiff(root);
       return res;
}
private void minDiff(TreeNode root) {
	if(root==null) {
 	   return ;
    }//设置基线条件 ,如果这棵树根节点为空,返回0
    //这里可以遍历一下这颗二叉树
    minDiff(root.left);
    minDiff(root.right);
    //记录左右的差值
    int leftMin=Integer.MAX_VALUE;
    int rightMin=Integer.MAX_VALUE;
    if(root.left!=null) {
    	leftMin=Math.abs(root.val-findMaxLeft(root.left));
    }
    if(root.right!=null) {
    	rightMin=Math.abs(root.val-findMaxRight(root.right));
    }
    int cur=Math.min(leftMin, rightMin);
    res=Math.min(res, cur);
}
private int findMaxLeft(TreeNode root) {
	//寻找以左节点为根节点的最大值
	if(root.right==null) {
		return root.val;
	}
	return findMaxLeft(root.right);
}
private int findMaxRight(TreeNode root) {
	//寻找以右左节点为根节点的最小值
	if(root.left==null) {
		return root.val;
	}
	return findMaxLeft(root.left);
}

老师麻烦帮我看一下,我觉得这道题思路是对的呀,为什么有4个测试用例通不过

写回答

1回答

liuyubobobo

2019-09-20

抱歉,我看不懂你的逻辑,能否把注释写的更清晰一些?

尤其是整个递归过程到底在做什么?

另外,比如 findMaxRight 这个函数明明叫 Max,为什么注释是 “寻找最小值”?


我的参考代码:(C++)

https://github.com/liuyubobobo/Play-Leetcode/tree/master/0783-Minimum-Distance-Between-BST-Nodes/cpp-0783


加油。

1
1
pfco
非常感谢!
2019-09-20
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程