上下翻转二叉树。题意是给一个二叉树,请你翻转一下。我的理解是基本是把这个二叉树顺时针旋转120度的感觉。例子,
Example:
Input: [1,2,3,4,5] 1 / \ 2 3 / \ 4 5 Output: return the root of the binary tree [4,5,2,#,#,3,1] 4 / \ 5 2 / \ 3 1
如上图,最小的左孩子成了根节点,而原来的根节点成了最小的右孩子。我这里给出递归的做法,首先找到新的根节点,然后将新的根节点跟他的左右孩子分别连好,然后再断开原来的根节点及其左右孩子的联系。
时间O(n)
空间O(n)
Java实现
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public TreeNode upsideDownBinaryTree(TreeNode root) { 18 // corner case 19 if (root == null || root.left == null && root.right == null) { 20 return root; 21 } 22 23 // normal case 24 TreeNode newRoot = upsideDownBinaryTree(root.left); 25 root.left.left = root.right; 26 root.left.right = root; 27 root.left = null; 28 root.right = null; 29 return newRoot; 30 } 31 }