897. 递增顺序查找树

DFS应用。

总结的DFS、BFS模板参考：https://www.cnblogs.com/panweiwei/p/13065661.html

class Solution(object):
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        # 获取树的中序序列
        res = self.mid_DFS(root)
        return self.CreateTree(res)

    # DFS中序遍历二叉树
    def mid_DFS(self, root):
        # 特判：树根为空
        if not root:
            return []
        # 返回值
        res = []
        res += self.mid_DFS(root.left)
        res.append(root.val)
        res += self.mid_DFS(root.right)
        return res

    # 构造单边二叉树
    def CreateTree(self,res):
        # 单边树的高度
        level = len(res)
        ans = root = TreeNode(0)
        poi = 0
        while level>poi:
            root.right = TreeNode(res[poi])
            root.left = None
            root = root.right
            poi += 1
        return ans.right