将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
方法一:中序遍历+修改指针
var fw, ans *TreeNode
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if fw == nil {
fw = root
ans = fw
} else {
fw.Right = root
root.Left = nil
fw = root
}
dfs(root.Right)
}
func increasingBST(root *TreeNode) *TreeNode {
fw, ans = nil, nil
dfs(root)
return ans
}
方法二:重新构造