search

larscheng / algo

0 stars 0 forks source link

【Check 52】2024-04-15 - 230. 二叉搜索树中第K小的元素 #154

Open larscheng opened 2 months ago

larscheng commented 2 months ago

230. 二叉搜索树中第K小的元素

larscheng commented 2 months ago

思路

class Solution { //中序遍历到第k个元素 public int kthSmallest(TreeNode root, int k) { Stack stack = new Stack<>(); while (root!=null||!stack.isEmpty()){ while (root!=null){ stack.push(root); root = root.left; }

        root = stack.pop();
        if (--k==0){
            break;
        }
        root = root.right;
    }
    return root.val;
}

}



### 复杂度
- 时间复杂度：O(h+k),h为树的高度
- 空间复杂度：O(h)