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

  • 0

    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;

Log in to reply

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