LeetCode 156 / LintCode 649 Binary Tree Upside Down

思路

根据题目中给出的树的要求：右节点要么为空，要么与左节点同时存在并且此时的右节点为叶子节点。
因此，本题要做的就是修改每个左节点的指向（除了原来的root）。由于本题中的树存在上面的性质，所以只需要修改左节点即可。递归搜索后修改指向即可。
【需要注意的是：为了保证原来的root与left和right之间在修改之后不会形成环，要加上root.left=null, root.right=null；递归的base case应该考虑root.left（稍加思考就能理解）】

代码

/*** 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;return reverse(root);}public TreeNode reverse(TreeNode root) {
    if(root.left == null) {
    return root;}TreeNode newRoot = reverse(root.left);root.left.left = root.right;root.left.right = root;// for the previous root node.root.left = null;root.right = null;return newRoot;}
}

复杂度

时间复杂度O(h)=O(logn)
空间复杂度O(h)=O(logn)