114. Flatten Binary Tree to Link

题目

给定一个二叉树的根 root，将这棵二叉树展开为链表。这个链表有两个特性

1. 链表节点由二叉树类表示，节点左节点置空
2. 链表的顺序和前序遍历相同。

解析

固定到一个节点来看，要将这颗子树展开成链表，首先将左子树展开成链表，然后将右子树展开成链表，最后将右子树的链表接在左子树上，即
f(node) = node -> f(node.left) -> f(node.right)
根据递归公式，递归函数返回子树的最后一个节点。
f(node) node

伪代码

res = node.right
node.right = node.left
last = f(node.left)
last.right = res
node.left = nil
return f(res)

代码

func flatten(root *TreeNode)  {
    if root == nil {
        return
    }
    f(root)
}

func f(node *TreeNode) *TreeNode {
    if node.Left == nil && node.Right == nil {
        return node
    }
    if node.Left == nil {
        return f(node.Right)
    }
    if node.Right == nil {
        node.Right = node.Left
        node.Left = nil
        return f(node.Right)
    }
    last := f(node.Left)
    
    res := node.Right
    node.Right = node.Left
    last.Right = res
    node.Left = nil
    return f(res)
}

后记

1. 代码写的很烂，看起来并不舒服，想不到更好的逻辑优化
2. 左子树和右子树都应该返回一个非空节点，那么就要保证传入的节点是一个非空的节点，在此基础上，需要对左右节点为空的情况做一个判断。

优化

后续简单优化了一下，在进行左右节点空判断的时候，将左或右空统一规划到左节点为空的情况，然后再根据左节点是否为空，进行额外操作，不影响整体逻辑。

func flatten(root *TreeNode)  {
    if root == nil {
        return
    }
    f(root)
}

func f(node *TreeNode) *TreeNode {
    if node.Left == nil && node.Right == nil {
        return node
    }
    if node.Right == nil {
        node.Right = node.Left
        node.Left = nil
    }
    
    res := node.Right
    if node.Left != nil {
        last := f(node.Left)
        node.Right = node.Left
        last.Right = res
        node.Left = nil
    }
    return f(res)
}