【二叉树专题】剑指 Offer 27. 二叉树的镜像-跟着帅地玩副业，开拓第二曲线PlayOffer

mpweixin用户普通 2024年12月14日下午4:07

递归
1、传入树根节点，传出翻转了左右子树的根节点
2、出口：根为空，直接返回
3、递归：左右子树交换，随后处理子树作为新的树根递归处理
时间O(N)，空间O(N)

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if(root == NULL) return root;
        swap(root->left, root->right);
        flipTree(root->left);
        flipTree(root->right);
        return root;
    }
};

0 赞同 0 条回复

岱永久会员 2024年12月11日下午3:58

LCR 144. 翻转二叉树

递归

class Solution {
    public TreeNode flipTree(TreeNode root) {
        return recur(root);
    }

    private TreeNode recur(TreeNode root){
        if(root == null) return null;

        recur(root.left);
        recur(root.right);

        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
        return root;
    }

}

队列

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();//出队列
            TreeNode t = node.left;
            node.left = node.right;
            node.right = t;
            if(node.left!=null)q.add(node.left);
            if(node.right!=null)q.add(node.right);
        }
        return root;
    }

}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月4日上午10:12

题解

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode newRight=flipTree(root.left);
        TreeNode newLeft=flipTree(root.right);
        root.left=newLeft;
        root.right=newRight;
        return root;
    }
}

0 赞同 0 条回复

🌟 普通 2024年12月3日下午8:07

“`cpp
没有动脑
class Solution {
public:
TreeNode* flipTree(TreeNode* root) {
if(!root) return nullptr;
TreeNode* temp=root->left;
root->left=root->right;
root->right=temp;
flipTree(root->left);
flipTree(root->right);
return root;
}
};
“`cpp

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午6:13

简单的递归

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root==null)return null;
        TreeNode tleft=flipTree(root.left);
        TreeNode tright=flipTree(root.right);
        root.left=tright;
        root.right=tleft;
        return root;
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年12月1日上午4:07

方法递归直接从root的左右开始递归，递归函数体中交换左右就能镜像
三部曲确实有用

class Solution:
    def flipTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return root
        left = self.flipTree(root.left)
        right = self.flipTree(root.right)

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

        return root

time O(n) space O(n)

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午7:31

/**
方法一：递归
 */
class Solution {
    public TreeNode flipTree(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        flipTree(root.left);
        flipTree(root.right);
        return root;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月29日下午12:19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root==null) return root;
        TreeNode left=flipTree(root.left);
        TreeNode right=flipTree(root.right);
        root.right=left;
        root.left=right;
        return root;
    }
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

黑键〰普通 2024年11月29日上午10:49

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var flipTree = function(root) {
    if(!root) return null;
    [root.left, root.right] = [flipTree(root.right), flipTree(root.left)];
    return root
};

思路：递归思想，确认终止条件是叶子结点为null，然后分别对左右子树进行递归。时间空间复杂度都是O(N)，要镜像就是要遍历所有节点

0 赞同 0 条回复

Renasc 普通 2024年11月28日下午10:23

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public TreeNode flipTree(TreeNode root) {
        // 如果为空，直接返回
        if (root == null) {
            return root;
        }

        // 翻转右子树，保存临时值
        TreeNode left = flipTree(root.right);
        // 翻转左子树，保存临时值
        TreeNode right = flipTree(root.left);

        // 赋值给root的左右子树
        root.left = left;
        root.right = right;

        // 返回
        return root;
    }
}

0 赞同 0 条回复

无言永久会员 2024年11月28日下午9:00

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if(root == nullptr) return root;
        TreeNode* rigthNode = flipTree(root->left);
        TreeNode* leftNode = flipTree(root->right);
        root->left = leftNode;
        root->right = rigthNode;
        return root;
    }
};
时间复杂度：O(N) 
空间复杂度：O(N)

0 赞同 0 条回复

苯庸普通 2024年11月28日下午8:14

class Solution {
public TreeNode flipTree(TreeNode root) {
if(root null){
return root;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
flipTree(root.left);
flipTree(root.right);
return root;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Aatorx 永久会员 2024年11月28日下午3:52

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        TreeNode* l = flipTree(root->left);
        TreeNode* r = flipTree(root->right);
        root->left = r;
        root->right = l;
        return root;
    }
};

递归反转二叉树
时间复杂度O(N),空间复杂度O(N)。

0 赞同 0 条回复

Kisara 普通 2024年11月28日下午2:42

递归遍历每一个节点然后交换左右子树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root==null) return root;

        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;

        flipTree(root.left);
        flipTree(root.right);

        return root;
    }
}

On On

0 赞同 0 条回复

Jerry 普通 2024年11月28日下午2:16

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if(!root) return root;
        TreeNode* leftChild = flipTree(root->left);
        TreeNode* rightChild = flipTree(root->right);
        root->left = rightChild;
        root->right =  leftChild;

        return root;
    }
};

时间/空间o(n)

0 赞同 0 条回复

月下足迹普通 2024年11月28日上午10:38

//时间复杂度O(N)

public TreeNode flipTree(TreeNode root) {

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

    TreeNode leftTree = flipTree(root.left);
    TreeNode righTree = flipTree(root.right);

    root.left = righTree;
    root.right = leftTree;

    return root;

}

0 赞同 0 条回复

jaron 普通 2024年11月28日上午10:11

时间复杂度：O(n)
空间：树的高度

// 自顶向下交换
class Solution {
    public TreeNode flipTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return root;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        flipTree(root.left);
        flipTree(root.right);
        return root;
    }
}

0 赞同 0 条回复

youngsir 普通 2024年11月28日上午9:21

打卡，先交换再修改

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        flipTree(root->left);
        flipTree(root->right);
        return root;

    }
};

时空复杂度O（n）

0 赞同 0 条回复

lQl 永久会员 2024年11月27日下午11:12

先交换,再递归修改

class Solution {
    public TreeNode flipTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        root.left = flipTree(root.left);
        root.right = flipTree(root.right);

        return root;
    }
}

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

休一普通 2024年11月27日下午9:25

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if (root == nullptr) return nullptr;

        // 翻转树
        TreeNode* leftFlipped = flipTree(root->left);
        TreeNode* rightFlipped = flipTree(root->right);

        // 交换他们
        root->left = rightFlipped;
        root->right = leftFlipped;

        // 返回父节点
        return root;
    }
};
//时间复杂度和空间复杂度均为o(n)

0 赞同 0 条回复

秋山丽奈普通 2024年11月27日下午8:24

思路：首先递归交换当前节点的左子树与右子树，之后将当前节点的左右子树信息交换

class Solution {
    public TreeNode flipTree(TreeNode root) {
        swap(root);
        return root;
    }

    public void swap(TreeNode root){
        if(root == null){
            return;
        }

        swap(root.left);
        swap(root.right);

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

0 赞同 0 条回复

晓宇普通 2024年11月27日下午8:18

class Solution {
public:
    TreeNode* flipTree(TreeNode* root) {
        if(!root || (!root->left && !root->right)) return root;
        TreeNode *lef = flipTree(root->left);
        TreeNode *rit = flipTree(root->right);
        root->left = rit;
        root->right = lef;
        return root;
    }
};
// 思路：递归，前序遍历（根左右）的思路
// 时间复杂度：o(n)
// 空间复杂度：o(lg n)

0 赞同 0 条回复

迢迢星野普通 2024年11月27日下午7:56

class Solution {
    /**
     * 给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。
     * @param root
     * @return
     */
    public TreeNode flipTree(TreeNode root) {
        mirrorTree(root);
        return root;
    }

    private TreeNode traverse(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode left = traverse(root.left);
        TreeNode right = traverse(root.right);
        // 后序位置进行翻转
        root.left = right;
        root.right = left;

        return root;
    }

    // 迭代法
    private TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 交换 node 的左右子树
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        return root;
    }
}

思路：递归（常规二叉树的递归方法）、迭代法（栈）
时间复杂度：两种方法的时间复杂度都是 O(n)。
空间复杂度：两种方法的空间复杂度都是 O(logn)（平均情况）或 O(n)（最坏情况）

0 赞同 0 条回复

【二叉树专题】剑指 Offer 27. 二叉树的镜像

共以下 23 个回答

LCR 144. 翻转二叉树

# 回答此问题取消回复

【二叉树专题】剑指 Offer 27. 二叉树的镜像

共以下 23 个回答

LCR 144. 翻转二叉树

# 回答此问题 取消回复

# 回答此问题取消回复