代码随想录算法训练营第十七天 | leetcode：二叉搜索树的最小绝对差 ,二叉搜索树中的众数,二叉树的最近公共祖先

_zzh 的个人博客 / 10 / 0 / 创建于 4个月前 / 更新于 4个月前

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;
        }
    }
}