# Java recursive solution: should be easier to understand than most soluations

• Basic idea is to find the leftmost leaf node and its parent. The leftmost leaf node is the newRoot, and we need to make its parent a leaf node by nullifying both leftmost leaf and leftmost leaf's sibling. Then we apply recursion to the root, and make the upside-downed' tree as the right node of the new root.

``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
// algorithm: classic recursion
if (null == root) {
return root;
} else if (null == root.left && null == root.right) {
return root;
} else {
// find the left most left node: that is the new root
TreeNode leftMostLeafParent = root;
TreeNode leftMostLeafNode = leftMostLeafParent.left;
while (null != leftMostLeafNode.left) {
leftMostLeafParent = leftMostLeafNode;
leftMostLeafNode = leftMostLeafNode.left;
}
// record leftMostLeafNodeSibling => new root's left child
TreeNode leftMostLeafNodeSibling = leftMostLeafParent.right;
// make leftMostLeafParent a leaf node!!!
leftMostLeafParent.left = null; leftMostLeafParent.right = null;
// and flip it -- recursion!
TreeNode treeFlippedWithOneLessLevel = upsideDownBinaryTree(root);
leftMostLeafNode.left = leftMostLeafNodeSibling;
leftMostLeafNode.right = treeFlippedWithOneLessLevel;
return leftMostLeafNode;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.