面试题 17.12. BiNode【二叉搜索树】【简单】【递归】

题目

代码

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func convertBiNode(root *TreeNode) *TreeNode {
    head, _ := dfs(root)
    return head
}

func dfs(root *TreeNode) (head, tail *TreeNode) {
    fmt.Printf("+++++++root is %v\n", root)

    // 递归停止条件
    if root == nil {
        return nil, nil
    }

    // 叶子节点
    if root.Left == nil && root.Right == nil {
        return root, root
    }

    lHead, lTail := dfs(root.Left)
    rHead, rTail  := dfs(root.Right)

    // 左子树为空
    if lHead != nil {
        head = lHead
        tail = lTail
        tail.Left = nil
        tail.Right = root
        tail = root
    } else {
        head = root
        tail = root
    }

    tail.Left = nil
    if rHead != nil {
        tail.Right = rHead
        tail = rTail
    }

    return
}