Binary Tree Upside Down leetcode

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

方法1: 类似reverse linkedlist, 从后往前一步一步的reverse

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode parent = null;
        TreeNode right = null;
        while (root != null) {
            TreeNode left = root.left;
            root.left = right;
            right = root.right;
            root.right = parent;
            parent = root;
            root = left;
        }
        return parent;
    }
}

方法2 用stack, 从前往后reverse

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack stack = new Stack();
        while (root.left != null) {
            stack.push(root);
            root = root.left;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (stack.isEmpty()) {
                node.left = null;
                node.right = null;
            } else {
                node.left = stack.peek().right;
                node.right = stack.peek();
            }
        }
        return root;
    }
}