Leetcode: binary tree upside down (II)

Oct. 24, 2017

Introduction

It only takes around 20 minutes to read a recursive solution on the panel of Leetcode discussion. I read the solution this morning around 3:00 am. Now it is 5:43 am, I got up and started to work on my computer and blog this algorithm.

Code study 

It is better for me to choose one of discussion, and check in the code, and then plan to write C# solution later. 

Here is the discussion link.

Analysis 

Most important is to read yfcheng's analysis. Plan to spend 20 minutes to read and also review the drawings. And then I will write down my own words, and make a drawing as well.

Java code 

Recursive solution in Java code:

	public TreeNode upsideDownBinaryTree(TreeNode root) {
	if(root == null || root.left == null) {
	return root;
	}
	TreeNode newRoot = upsideDownBinaryTree(root.left);
	root.left.left = root.right; // node 2 left children
	root.left.right = root; // node 2 right children
	root.left = null;
	root.right = null;
	return newRoot;
	}

view raw upsideDownBinaryTree.java hosted with ❤ by GitHub

Iterative solution in Java code:

	public TreeNode upsideDownBinaryTree(TreeNode root) {
	TreeNode curr = root;
	TreeNode next = null;
	TreeNode temp = null;
	TreeNode prev = null;
	while(curr != null) {
	next = curr.left;
	// swapping nodes now, need temp to keep the previous right child
	curr.left = temp;
	temp = curr.right;
	curr.right = prev;
	prev = curr;
	curr = next;
	}
	return prev;
	}

view raw upsideDownBinaryTree_Iterative.java hosted with ❤ by GitHub

Actionable Item

I finished the blog at 6:00 AM, only 15 minutes. Will come back to work on the algorithm based on the discussion.