LC114 - 二叉树展开为链表

package BinaryTree

func flatten(root *TreeNode) {
    cur := root
    for cur != nil {
        leftChild := cur.Left
        rightChild := cur.Right
        if leftChild != nil {
            rightMost := findRightMost(leftChild)
            cur.Left = nil
            cur.Right = leftChild
            rightMost.Right = rightChild
        }
        cur = cur.Right
    }
}

func findRightMost(node *TreeNode) *TreeNode {
    var pre *TreeNode = nil
    for node != nil {
        pre = node
        if node.Right != nil {
            node = node.Right
        } else {
            node = node.Left
        }
    }
    return pre
}

将左子树插入到当前节点和右子树之间，同时右子树连到左子树最右节点处。