leetcode 226 Invert Binary Tree 翻转二叉树

大牛没有能做出来的题，我们要好好做一做

Invert a binary tree.

     4

   /   \

  2     7

 / \   / \

1   3 6   9

     4

   /   \

  7     2

 / \   / \

9   6 3   1

Trivia:

This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

递归解决方案：

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* invertTree(TreeNode* root)

    {

        if(root ==NULL) return root;

        TreeNode* node = invertTree(root->left);

        root->left = invertTree(root->right);

        root->right = node;

        return root;

    }

};

非递归解决方案：

 TreeNode* invertTree(TreeNode* root)

    {

        if(root == NULL)return NULL;

        vector<TreeNode*> stack;

        stack.push_back(root);

        while(!stack.empty())

        {

            TreeNode* node = stack.back();// or stack.top()

            stack.pop_back();

            swap(node->left,node->right);

            if(node->left)stack.push_back(node->left);

            if(node->right)stack.push_back(node->right);

        }

        return root;

    }

python：

def invertTree(self, root):

    if root:

        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

        return root

Maybe make it four lines for better readability:

def invertTree(self, root):

    if root:

        invert = self.invertTree

        root.left, root.right = invert(root.right), invert(root.left)

        return root

--------------------------------------------------------------------------------

And an iterative version using my own stack:

def invertTree(self, root):

    stack = [root]

    while stack:

        node = stack.pop()

        if node:

            node.left, node.right = node.right, node.left

            stack += node.left, node.right

    return root

def invertTree(self, root):

    if root is None:

        return None

    root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

    return root

python非递归解决方案：

DFS version:

def invertTree(self, root):

        if (root):

            self.invertTree(root.left)

            self.invertTree(root.right)

            root.left, root.right = root.right, root.left

            return root   

BFS version:

def bfs_invertTree(self, root):

        queue = collections.deque()

        if (root):

            queue.append(root)

        while(queue):

            node = queue.popleft()

            if (node.left):

                queue.append(node.left)

            if (node.right):

                queue.append(node.right)

            node.left, node.right = node.right, node.left

        return root

巴特西

leetcode 226 Invert Binary Tree 翻转二叉树

最新文章

热门文章