Leetcode PHP题解--D96 530. Minimum Absolute Difference in BST
D96 530. Minimum Absolute Difference in BST
题目链接
530. Minimum Absolute Difference in BST
题目分析
给定一个二叉树,返回任意两节点的最小差。
思路
先获取所有节点值,再逐个比对。不过这样效率很低。
最终代码
<?php
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
protected $values = [];
/**
* @param TreeNode $root
* @return Integer
*/
function getMinimumDifference($root) {
$this->preOrder($root);
$amount = count($this->values);
$minValue = 9999999;
for($i=0; $i<$amount; $i++){
for($j=$i+1;$j<$amount; $j++){
$diff = abs($this->values[$i] - $this->values[$j]);
if($diff<$minValue){
$minValue = $diff;
}
}
}
return $minValue;
}
function preOrder($root){
if(is_null($root->val)){
return;
}
$this->values[] = $root->val;
if($root->left){
$this->preOrder($root->left);
}
if($root->right){
$this->preOrder($root->right);
}
}
}
若觉得本文章对你有用,欢迎用爱发电资助。
No Comments