D97 783. Minimum Distance Between BST Nodes
题目链接
783. Minimum Distance Between BST Nodes
题目分析
给定一个二叉树,返回任意两节点的最小差。
思路
先获取所有节点值,再逐个比对。不过这样效率很低。
最终代码
<?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 {
/**
* @param TreeNode $root
* @return Integer
*/
function minDiffInBST($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);
}
}
}
若觉得本文章对你有用,欢迎用爱发电资助。