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

2019-4-30 星期二  开始吧

上一题链接 Leetcode基础刷题之PHP解析(268. Missing Number)

题目描述

给定一个二叉查找树，查找出第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