leetcode 530. Minimum Absolute Difference in BST
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:
Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).Note: There are at least two nodes in this BST.
WA:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int travel1(struct TreeNode* root) { if(root->left!=NULL) { return travel1(root->left); } else { return root->val; } } int travel2(struct TreeNode* root) { if(root->left!=NULL) { return travel1(root->left); } else if(root->right!=NULL) { return travel1(root->right); } else { return grandfather node val; ///此处无法实现。。。。。 } } int getMinimumDifference(struct TreeNode* root) { int minValue1,minValue2; minValue1=travel1(root); minValue2=travel2(root); return abs(minValue1-minValue2); }
WA:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int A[1000000]; int length=0; int travel(struct TreeNode* root) { if(root->left!=NULL) { travel(root->left); } A[length]=root->val; length++; if(root->right!=NULL) { travel(root->right); } return 0; } int getMinimumDifference(struct TreeNode* root) { travel(root); int min=abs(A[0]-A[1]); for(int i=1;i<length-1;i++) { if(min>abs(A[i]-A[i+1])) { min=abs(A[i]-A[i+1]); } } return min; }
tip： 第二次提交时，出现下面的情况，不知道是不是bug
WA:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int getMinimumDifference(struct TreeNode* root) { if(root==NULL) { return 0; } int leftDiff=65536,rightDiff=65536,leftmin=0,rightmin=0; if(root->left!=NULL) { leftDiff=getMinimumDifference(root->left); leftmin=root->left->val; } if(root->right!=NULL) { rightDiff=getMinimumDifference(root->right); rightmin=root->right->val; } int result=leftDiff<rightDiff?leftDiff:rightDiff; if(root->left!=NULL) { leftDiff=abs(root->val-leftmin); result=leftDiff<result?leftDiff:result; } if(root->right!=NULL) { rightDiff=abs(root->val-rightmin); result=result<rightDiff?result:rightDiff; } if(root->left!=NULL&&root->val>leftmin) { root->val=leftmin; } if(root->right!=NULL&&root->val>rightmin) { root->val=rightmin; } return result; }
tips:想之前一篇文章一样，递归，修改树原来的值，每次递归中根节点值修改为其所有子树中的最小值，但是还是错了。
我觉得这个应该是对的，中序排序
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int A[100000]; int length=0; void travel(struct TreeNode* root) { if(root==NULL) { return ; } if(root->left!=NULL) { travel(root->left); } A[length]=root->val; length++; if(root->right!=NULL) { travel(root->right); } } int compare(const void *a,const void *b) { return *(int *)a-*(int *)b; } int getMinimumDifference(struct TreeNode* root) { travel(root); qsort(A,length,sizeof(A[0]),compare); int result=abs(A[0]-A[1]); for(int i=1;i<length-1;i++) { if(result>abs(A[i]-A[i+1])) { result=abs(A[i]-A[i+1]); } } return result; }
测试代码过了，递交代码错了，但是递交不过的样例和测试代码的输入样例是一样的，所以我觉得是检测程序的bug
