[LeetCode] 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},

/ \

2 3

/ \

4 5

return the root of the binary tree [4,5,2,#,#,3,1].

/ \

5 2

/ \

3 1

给一个二叉树，右节点要么为空要么一定会有对应的左节点，把二叉树上下颠倒一下，原二叉树的最左子节点变成了根节点，其对应的右节点变成了其左子节点，其父节点变成了其右子节点。

解法1：递归

解法2：迭代

Java: Time: O(N), Space: O(N)

public class Solution {

    public TreeNode upsideDownBinaryTree(TreeNode root) {

        if(root == null || root.left == null)return root;

        TreeNode newRoot = upsideDownBinaryTree(root.left);

        //root.left is newRoot everytime

        root.left.left = root.right;

        root.left.right = root;

        root.left = null;

        root.right = null;

        return newRoot;

    }

}

Java: Time: O(N), Space: O(1)

public class Solution {

    public TreeNode upsideDownBinaryTree(TreeNode root) {

        TreeNode cur = root;

        TreeNode pre = null;

        TreeNode tmp = null;

        TreeNode next = null;

        while(cur != null){

            next = cur.left;

            //need tmp to keep the previous right child

            cur.left = tmp;

            tmp = cur.right;

            cur.right = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

Python:

# Time:  O(n)

# Space: O(n)

class Solution2(object):

    # @param root, a tree node

    # @return root of the upside down tree

    def upsideDownBinaryTree(self, root):

        return self.upsideDownBinaryTreeRecu(root, None)

    def upsideDownBinaryTreeRecu(self, p, parent):

        if p is None:

            return parent

        root = self.upsideDownBinaryTreeRecu(p.left, p)

        if parent:

            p.left = parent.right

        else:

            p.left = None

        p.right = parent

        return root

Python:

class Solution(object):

    # @param root, a tree node

    # @return root of the upside down tree

    def upsideDownBinaryTree(self, root):

        p, parent, parent_right = root, None, None

        while p:

            left = p.left

            p.left = parent_right

            parent_right = p.right

            p.right = parent

            parent = p

            p = left

        return parent

C++:

// Recursion

class Solution {

public:

    TreeNode *upsideDownBinaryTree(TreeNode *root) {

        if (!root || !root->left) return root;

        TreeNode *l = root->left, *r = root->right;

        TreeNode *res = upsideDownBinaryTree(l);

        l->left = r;

        l->right = root;

        root->left = NULL;

        root->right = NULL;

        return res;

    }

};

C++:

// Iterative

class Solution {

public:

    TreeNode *upsideDownBinaryTree(TreeNode *root) {

        TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;

        while (cur) {

            next = cur->left;

            cur->left = tmp;

            tmp = cur->right;

            cur->right = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

};

巴特西

[LeetCode] 156. Binary Tree Upside Down 二叉树的上下颠倒

最新文章

热门文章