Leetcode基础刷题之PHP解析(230. Kth Smallest Element in a BST)


2019-4-30 期二  

 Leetcode基础刷题之PHP解析(268. Missing Number)

51c7417c97a610ebed06cdad85859e8b.png

给定一个二叉查找树,查找出第k小的结点值。

因为是二叉查找树,可以通过中序遍历把值存入一个定义的数组中,那么就好办了。缺点是浪费空间.

/**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($root, $k) {
         $res=[];
        $this->sortNode($root,$res); 
        return $res[$k-1];
    }
    
    function sortNode($root,&$res){
        
        if($root==null){
            return $res;
        }
        $this->sortNode($root->left,$res);
        array_push($res,$root->val);
        $this->sortNode($root->right,$res);
    }

第二种

使用迭代也是可以的。利用栈的特性,因为是二叉排序树,每次拿出一个结点,当拿到第k个结点时,说明当前就是第k小的值。

 /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($root, $k) {
        $res=[];
        while(true){
            while($root !==null){
                array_unshift($res,$root);
                $root=$root->left;
            }
            $root=array_shift($res);
            if(--$k==0) return $root->val;
            $root=$root->right;
        }
    }
    

Github整理地址:https://github.com/wuqinqiang/leetcode-php



Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D47 868. Binary Gap

>> 下一篇: Leetcode PHP题解--D48 985. Sum of Even Numbers After Queries