114. 二叉树展开为链表 Krains 2020-08-02 08:59:00 树

class Solution {
    TreeNode pre = null;

    public void flatten(TreeNode root) {
        if(root == null)
            return ;
        TreeNode l = root.left;
        TreeNode r = root.right;

        // 左子树清空
        root.left = null;
        // 如果当前root不是根结点，pre就不为null
        if(pre != null){
            pre.right = root;
        }
        // 记录先序遍历的前一个结点
        pre = root;
        
        flatten(l);
        flatten(r);
    }
}

class Solution {
    public void flatten(TreeNode root) {
        helper(root);
    }

    public TreeNode helper(TreeNode root){
        if(root == null)
            return null;
        TreeNode l = helper(root.left);
        TreeNode r = helper(root.right);
        root.right = l;
        root.left = null;

        // 将右孩子放在root链表的末尾
        TreeNode t = root;
        while(t.right != null){
            t = t.right;
        }
        t.right = r;
        
        return root;
    }
}