题解 | #二叉搜索树的第k个结点# golang
二叉搜索树的第k个结点
http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a
func KthNode( pRoot *TreeNode , k int ) *TreeNode { // write code here if pRoot == nil || k <= 0 { return nil } stack := NewStack() cul := pRoot for !stack.IsEmpty() || cul != nil { if cul != nil { stack.Push(cul) cul = cul.Left } else { cul = stack.Pop() k-- if k==0 { return cul } cul = cul.Right } } return nil } type Stack struct { Val []*TreeNode Top int } func NewStack() *Stack { return &Stack{Val:make([]*TreeNode,0),Top: 0} } func (s *Stack) Push(v *TreeNode) { s.Top++ s.Val = append(s.Val, v) } func (s *Stack) Pop() *TreeNode { if s.Top==0 { return nil } v:=s.Val[s.Top-1] s.Val = s.Val[:s.Top-1] s.Top-- return v } func (s *Stack) IsEmpty() bool { if s.Top == 0 { return true } return false }