代码随想录算法训练营第十七天 | leetcode：二叉搜索树的最小绝对差 ,二叉搜索树中的众数,二叉树的最近公共祖先
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
530. 二叉搜索树的最小绝对差
解题方法
思路：因为是二叉搜索树，所以使用中序遍历。需要新增一个pre指针，记录上一次遍历的节点。在遍历过程中，不断计算pre与当前遍历节点cur的差值，并且与上一次计算结果比较取较小值。
code
递归法
class Solution {
private $pre;
private $result;
/**
* @param TreeNode $root
* @return Integer
*/
function getMinimumDifference($root) {
$this->result = PHP_INT_MAX;
$this->traversal($root);
return $this->result;
}
function traversal($node){
if($node == null) return;
$this->traversal($node->left);
//注意判断pre!=null ,再比较已有差值和当前差值，取最小值
if($this->pre != null) $this->result = min($this->result, $node->val - $this->pre->val);
//记录上一个节点
$this->pre = $node;
$this->traversal($node->right);
}
}501. 二叉搜索树中的众数
解题方法
思路：与上题一样，还是用到了双指针解题。
- 当pre指针=null时，也就是cur指针处在叶子节点，此时初始化count=1；
- 当pre == cur时，此时count++;
- 当pre再次不等于cur时，重置count=1；
- count与maxcount比较，更新较大值。
code
递归法
class Solution {
private $result = [];
private $maxCount = 0;
private $count = 0;
private $pre;
/**
* @param TreeNode $root
* @return Integer[]
*/
function findMode($root) {
$this->traversal($root);
return $this->result;
}
function traversal($node){
if($node == null) return;
$this->traversal($node->left);
//代表此时node在叶子节点
if($this->pre == null){
$this->count = 1;
}elseif($this->pre->val == $node->val){
//碰到相同元素计数++
$this->count++;
}else{
//碰到不同元素重置为1
$this->count = 1;
}
//更新慢指针
$this->pre = $node;
//收集结果
if($this->count == $this->maxCount){
$this->result[] = $node->val;
}
//如果出现比maxcount更大的值则更新maxcount,并重置result,再次收集结果
if($this->count > $this->maxCount){
$this->maxCount = $this->count;
$this->result = [$node->val];
}
$this->traversal($node->right);
}
}236. 二叉树的最近公共祖先
解题方法
使用后续遍历，判断当前遍历节点的状态：
- 当前节点是空节点，返回当前节点。
- 当前节点是 p，返回当前节点。
- 当前节点是 q，返回当前节点。
- 其他情况：
4.1 左右子树都找到:返回当前节点
4.2 只有左子树找到:返回递归左子树的结果
4.3 只有右子树找到:返回递归右子树的结果
4.4 左右子树都没有找到:返回空节点
code
class Solution {
/**
* @param TreeNode $root
* @param TreeNode $p
* @param TreeNode $q
* @return TreeNode
*/
function lowestCommonAncestor($root, $p, $q) {
//状态1,2,3
if($root == $p || $root == $q || $root == null) return $root;
//递归子树
$left = $this->lowestCommonAncestor($root->left, $p, $q);
$right = $this->lowestCommonAncestor($root->right, $p, $q);
//状态4.1
if ($left != NULL && $right != NULL) return $root;
//状态4.3
if ($left == NULL && $right != NULL) return $right;
//状态4.2
else if ($left != NULL && $right == NULL) return $left;
//状态4.4
else { // (left == NULL && right == NULL)
return NULL;
}
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号