算法-翻转二叉树

算法-翻转二叉树

文章目录

翻转

翻转二叉树翻转等价二叉树上下翻转二叉树

翻转 翻转二叉树

翻转二叉树（简单）
先序就是自上而下的翻转
后序就是自下而上的翻转
都可以，但是不能中序！

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }

    
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

翻转等价二叉树

添加链接描述

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
            if(root1==null && root2==null){
                return true;
            }
            if(root1==null || root2==null){
                return false;
            }
            if(root1.val!=root2.val){
                return false;
            }
            //不翻转 || 翻转 
            return 
            (flipEquiv(root1.left,root2.left) && flipEquiv(root1.right,root2.right)) 
            ||
             (flipEquiv(root1.left,root2.right) && flipEquiv(root1.right,root2.left));
    }
}

上下翻转二叉树

添加链接描述
思露：
首先确定：是从下往上翻转，只需考虑左子树，右子树只会有一个节点
然后：翻转之后返回新的根节点，父子树根节点是拼接在翻转之后的左子树的最右孩子节点下面的。

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root==null){
            return null;
        }
        return reverseTree(root);
    }

    private TreeNode reverseTree(TreeNode root) {
        if (root.left==null){
            return root;
        }
       
        TreeNode newRoot=reverseTree(root.left);//拿到翻转之后的左子树的根节点
        TreeNode r=newRoot;
        while (r.right!=null){ //找到左子树的最右孩子节点
            r=r.right;
        }
        r.left=root.right;
        r.right=root;
        root.left=null;
        root.right=null;
        return newRoot;
    }
}