LeetCode—— 翻转二叉树

题目描述

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

一、CPP

1. 递归法：

解题思路:前序递归遍历树，对树的操作代码交换左右子树即可。
时间复杂度:O(n)。每个元素都必须访问一次，n为元素个数。
空间复杂度:O(h)。h为树的高度，最坏的情况下，需要存放O(h)个函数调用。

/**
 * 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 * tmp_node;
        
        //前序遍历交换左右子树
        tmp_node = root->left;
        root->left = root->right;
        root->right = tmp_node;

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

        return root;
    }
};

2. 迭代法（层次遍历）：

解题思路:递归实现也就是深度优先遍历的方式，那么对应的就是广度优先遍历。广度优先遍历需要额外的数据结构--队列，来存放临时遍历到的元素。
深度优先遍历的特点是一竿子插到底，不行了再退回来继续；而广度优先遍历的特点是层层扫荡。所以，我们需要先将根节点放入到队列中，然后不断的迭代队列中的元素。对当前元素调换其左右子树的位置，然后：

• 判断其左子树是否为空，不为空就放入队列中
• 判断其右子树是否为空，不为空就放入队列中

时间复杂度:O(n)，每个节点都需要入队列/出队列一次。
空间复杂度:O(n)，最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是n/2个。

/**
 * 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) {

        queue<TreeNode*> myqueue;
        TreeNode *r, *tmp_node;

        if(!root){
            return root;
        }

        myqueue.push(root);

        while(!myqueue.empty()){
            r = myqueue.front();
            myqueue.pop();

            tmp_node = r->left;
            r->left = r->right;
            r->right = tmp_node;

            if(r->left){
                myqueue.push(r->left);
            }

            if(r->right){
                myqueue.push(r->right);
            }
        }

        return root;
        
    }
};

参考自：图解算法

二、Java（迭代法）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {

        if(root == null){
            return root;
        }

        Queue<TreeNode> myqueue = new LinkedList<>();
        TreeNode tmp_node = new TreeNode(0);
        TreeNode r = new TreeNode(0);

        myqueue.offer(root);

        while(!myqueue.isEmpty()){

            r = myqueue.poll();
            tmp_node = r.left;
            r.left = r.right;
            r.right = tmp_node;

            if(r.left!=null){
                myqueue.offer(r.left);
            }

            if(r.right!=null){
                myqueue.offer(r.right);
            }
        }

        return root;
        
    } 
}

三、Python（迭代法）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return root

        myqueue = []
        myqueue.append(root)

        while len(myqueue):
            r = myqueue.pop(0)

            tmp_node = r.left
            r.left = r.right
            r.right = tmp_node

            if r.left:
                myqueue.append(r.left)
            if r.right:
                myqueue.append(r.right)
        return root

四、各语言及算法时间复杂度