当前位置 博文首页 > 中流击水,浪遏飞舟:剑指 Offer 27. 二叉树的镜像

    中流击水,浪遏飞舟:剑指 Offer 27. 二叉树的镜像

    作者:[db:作者] 时间:2021-08-26 12:47

    参考:

    深入学习二叉树(一) 二叉树基础

    区别前中后序:

    从树型图看,第1次遍历到达该结点就进行操作:前序,第2次遍历到达该结点才进行操作:中序,第3次到达该结点才进行操作:后序;
    从递归代码块上看,操作代码放在left前面:前序,操作代码放在leftright中间:中序,操作代码放在right后面:后序。

    此题前序遍历和后序遍历都可以完成操作,中序遍历不行,中序遍历只能交换第2层的两个结点。

    前序遍历解法:

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            if(!root){
                return root;
            }
            TreeNode*temp=root->left;
            root->left=root->right;
            root->right=temp;
            mirrorTree(root->left);
            mirrorTree(root->right);
            return root;
        }
    };
    

    后续遍历解法:

    class Solution {
    public:
        TreeNode* mirrorTree(TreeNode* root) {
            if(!root){
                return root;
            }
            mirrorTree(root->left);
            mirrorTree(root->right);
            TreeNode*temp=root->left;
            root->left=root->right;
            root->right=temp;
            return root;
        }
    };
    
    cs