230.md

✏️Leetcode基础刷题之(230. Kth Smallest Element in a BST)

2019-04-30 吴亲库里 库里的深夜食堂

---

✏️描述

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

联系

​