首页 > 代码库 > 156. Binary Tree Upside Down
156. 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
链接: http://leetcode.com/problems/binary-tree-upside-down/
6/14/2017
1ms, 10%
我以为自己做不出来,结果居然很快做出来了,厚积薄发了嘿嘿。思路是,自底向上,left-root-right变为oldRight-oldLeft-oldRoot,并且上层的parent和right放在新的左子树的最右边节点。
注意,第17,18行需要将原来root的左右指针设为null
问题,第12行被使用过吗?还是说在题目给定条件下不会被用到?
希望自己能准确判断和使用top-down, bottom-up
1 public class Solution { 2 public TreeNode upsideDownBinaryTree(TreeNode root) { 3 if (root == null) { 4 return null; 5 } 6 7 if (root.left == null && root.right == null) { 8 return root; 9 } 10 11 TreeNode newLeft = upsideDownBinaryTree(root.left); 12 TreeNode newRight = upsideDownBinaryTree(root.right); 13 setNewUpsideDownTree(newLeft, root, newRight); 14 return newLeft; 15 } 16 private void setNewUpsideDownTree(TreeNode newRoot, TreeNode oldRoot, TreeNode newRight) { 17 oldRoot.left = null; 18 oldRoot.right = null; 19 while (newRoot.right != null) { 20 newRoot = newRoot.right; 21 } 22 newRoot.right = oldRoot; 23 newRoot.left = newRight; 24 } 25 }
别人的做法,包括recursive和iterative
https://discuss.leetcode.com/topic/40924/java-recursive-o-logn-space-and-iterative-solutions-o-1-space-with-explanation-and-figure
recursive
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; }
iterative
prev, temp相当于2个来自之前层的指针,比其他linkedlist多了一个prev,next指向下一层将要成为root的节点
1 public TreeNode upsideDownBinaryTree(TreeNode root) { 2 TreeNode curr = root; 3 TreeNode next = null; 4 TreeNode temp = null; 5 TreeNode prev = null; 6 7 while(curr != null) { 8 next = curr.left; 9 10 // swapping nodes now, need temp to keep the previous right child 11 curr.left = temp; 12 temp = curr.right; 13 curr.right = prev; 14 15 prev = curr; 16 curr = next; 17 } 18 return prev; 19 }
更多讨论
https://discuss.leetcode.com/category/165/binary-tree-upside-down
156. Binary Tree Upside Down