226. 翻转二叉树

1.题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

2.示例

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
1
2

3.答案

①递归

停止条件: 结点为空或者无孩子
递归内容: 左孩子翻转，右孩子翻转，左右孩子互换
返回值: 根节点

 TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;   //空节点直接返回
        if(!root->left&&!root->right) return root;  //只有一个节点直接返回
         //递归
         TreeNode*l=invertTree(root->left);  //左孩子翻转
         TreeNode*r=invertTree(root->right);  //右孩子翻转
         root->left=r;  //交换左右孩子
         root->right=l;
         return root;
    }
1
2
3
4
5
6
7
8
9
10

②迭代

从上向下，一层一层遍历，不断交换每个结点的左右孩子，使用层次遍历，因为每个结点只经过一次。

TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;   //空节点直接返回
        if(!root->left&&!root->right) return root;  //只有一个节点直接返回
		 //迭代实现
        ///交换每一层节点的左右孩子
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *node=q.front();  //取出队列头
            q.pop();
            TreeNode *tmp=node->left;  //交换左右孩子
            node->left=node->right;
            node->right=tmp;  
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18