[LeetCode] Binary Tree Upside Down的三種解法

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

這題有一個重要的限制就是，整個數的任何一個右孩子都不會再生枝節，基本就是一個梳子的形狀。對於樹類型的題目，首先可以想到一種遞歸的思路：把左子樹繼續顛倒，顛倒完後，原來的那個左孩子的左右孩子指針分別指向原來的根節點以及原來的右兄弟節點即可。

	public TreeNode UpsideDownBinaryTree(TreeNode root) {
		if (root == null)
			return null;
		TreeNode parent = root, left = root.left, right = root.right;
		if (left != null) {
			TreeNode ret = UpsideDownBinaryTree(left);
			left.left = right;
			left.right = parent;
			return ret;
		}
		return root;
	}

第二個思路是直接用迭代代替遞歸，做起來也不麻煩，並且效率會更高，因為省去了遞歸所用的棧空間。

	public TreeNode UpsideDownBinaryTree(TreeNode root) {
		TreeNode node = root, parent = null, right = null;
		while (node != null) {
			TreeNode left = node.left;
			node.left = right;
			right = node.right;
			node.right = parent;
			parent = node;
			node = left;
		}
		return parent;
	}

第三個思路比較特別，把後續遍歷轉換成層次遍歷。注意由於Java不支持對TreeNode地址傳引用，所以這裡弄了一個全局變量。另外，類似於對鏈表的處理，這裡我弄了一個dummy node簡化對根節點的處理。

	private TreeNode out = null;
	public TreeNode UpsideDownBinaryTree(TreeNode root) {	
		TreeNode dummy = new TreeNode(0);
		dummy.left = new TreeNode(0);
		out = dummy;
		
		postorder(root);
		return dummy.right;
	}
		
	private void postorder(TreeNode root) {
		if (root == null)
			return;
		
		postorder(root.left);
		postorder(root.right);
		
		if (out.left == null) {
			out.left = root;
			out.left.left = null;
			out.left.right = null;
		} else if (out.right == null) {
			out.right = root;
			out.right.left = null;
			out.right.right = null;
		}
		
		if (out.left != null && out.right != null)
			out = out.right;
	}