public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null  root.left == null && root.right == null)
return root;
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right;
root.left.right = root;
root.left = null;
root.right = null;
return newRoot;
}
Clean Java solution


C++ implementation of your method
class Solution { public: TreeNode* upsideDownBinaryTree(TreeNode* root) { if(root == NULL  (root>left == NULL && root>right == NULL) ) return root; TreeNode* new_root = upsideDownBinaryTree(root>left); root>left>left = root>right; root>left>right = root; root>left = NULL; root>right = NULL; return new_root; } };

@yubad2000 said in Clean Java solution:
What if the root node only has child on the right so that roo>left == null?
That is not possible as the question clearly states "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"


@jeantimex said in Clean Java solution:
if (root == null  root.left == null && root.right == null)
actually you can change this line to
if (root == null  root.left == null)
because if the left child is null, then the right child must be null.

@chidong Because the node you return is newRoot, which will always be the left most node. You can not modify it multiple times.

what if the root has only 2 children? Wouldn't root.left.left be null?
It's OK to be null, because you are assigning to it instead of referencing it. The root.left is ensured not null as it is checked at the very beginning.
I have another question for the author though, why do you need
&& root.right == null
. if root.left is null, root.right is guaranteed to be null, isn't it?

Can you explain what if the tree is like following shape?
1 / \ 2 3 / / \ 4 5 6
I think this tree is qualified with the definition of the problem.
But your solution will return4 \ 2 / \ 3 1 / \ 5 6
while the Node 6 is still a right node.
So my solution is very similar to you, but add one line to rotate root.right too:/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode upsideDownBinaryTree(TreeNode root) { if (root == null) { return null; } if (root.left == null) { return root; } TreeNode newRoot = upsideDownBinaryTree(root.left); TreeNode newLeft = upsideDownBinaryTree(root.right); // This line rotate the right node root.left.left = newLeft; root.left.right = root; root.left = null; root.right = null; return newRoot; } }
Both of our solutions can pass the OJ, I just want to know if there any parts I misunderstand.