package test30_kth

import (
    "fmt"
    "testing"
)

//Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

//BST 的中序遍历是升序序列
//go test -v -test.run TestKth
func TestKth(t *testing.T) {
    root := &TreeNode{}
    root.Val = 3
    root.Right = &TreeNode{}
    root.Right.Val = 4
    root.Left = &TreeNode{}
    root.Left.Val = 1
    root.Left.Right = &TreeNode{}
    root.Left.Right.Val = 2
    ret := kthSmallest1(root, 2)
    fmt.Println("递归法：", ret)
    ret = kthSmallest2(root, 2)
    fmt.Println("迭代法：", ret)
}

//递归法
//时间复杂度：O(N)，遍历了整个树。
//空间复杂度：O(N)，用了一个数组存储中序序列。
func kthSmallest1(root *TreeNode, k int) int {
    nums := inorder(root, &[]int{})
    return (*nums)[k-1]
}
func inorder(root *TreeNode, arr *[]int) *[]int {
    if root == nil {
        return arr
    }
    inorder(root.Left, arr)       //左
    *arr = append(*arr, root.Val) //根
    inorder(root.Right, arr)      //右
    return arr
}

//迭代法
//时间复杂度：O(H+k)，其中 H 指的是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为 O(logN+k)。当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。
//空间复杂度：O(H+k)。当树是一个平衡树时：O(logN+k)。当树是一个非平衡树时：O(N+k)。
func kthSmallest2(root *TreeNode, k int) int {
    stack := make([]*TreeNode, 0)
    for {
        for root != nil {
            //push
            stack = append(stack, root)

            root = root.Left
        }

        //pop
        root = stack[len(stack)-1]
        stack = stack[0 : len(stack)-1]

        k = k - 1
        if k == 0 {
            return root.Val
        }
        root = root.Right
    }
}