2019-08-23 剑指 二叉搜索树的第k个结点

20min，通过不了的时候拿着单独的样例在脑海里跑一遍就发现是把中序遍历写成了后序遍历。
如果不计数的话利用静态变量来记录index

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot:TreeNode, k):
        return self.dfs(pRoot,[k])

    def dfs(self,pRoot:TreeNode,res:List):
        if not pRoot:return None
        a=self.dfs(pRoot.left,res)
        if a:return a
        res[0]-=1
        if res[0]==0:return pRoot
        b=self.dfs(pRoot.right,res) # 中序遍历写成了后序遍历
        return b

if __name__ == '__main__':
    t=Solution()
    root=TreeNode(2)
    a=TreeNode(1)
    b=TreeNode(3)
    root.left=a
    root.right=b
    print(t.KthNode(root,1).val)
    print(t.KthNode(root,2).val)
    print(t.KthNode(root,3).val)