【算法系列-二叉树】对称翻转二叉树

【算法系列-二叉树】对称&翻转二叉树

1. 对称二叉树

【题目链接】101. 对称二叉树 - 力扣（LeetCode）

1.1 思路分析

这道题需要我们判断当前二叉树是否轴对称，我们需要将它翻译成更细致的理解：

在二叉树中：

判断树的外侧：左节点的左节点与右节点的右节点是否相同；

判断树的内侧：左节点的右节点与右节点的左节点是否相同；

理解了上述内容后，我们就能很好的写出代码来：

递归版本

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return judge(root.left, root.right);
    }

    boolean judge(TreeNode left, TreeNode right) {

        if (left == null && right != null) {
            return false;
        }
        else if (left != null && right == null) {
            return false;
        }
        else if (left == null && right == null) {
            return true;
        }
        else if (left.val != right.val) {
            return false;
        }
        // 能到这里则表示左右节点的结构和值是相同的
        boolean outFlag = judge(left.left, right.right);
        boolean inFlag = judge(left.right, right.left);
        return outFlag && inFlag;
    }
}

除了使用递归来解决，我这里再提供一个使用 层序遍历 + 双指针 解决问题的思路：

对二叉树进行层序遍历，每遍历一层时，将一层的节点都加入一个集合，通过左右双指针的方式遍历这个集合，只要有一个左右节点不相等即不对称

代码示例

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode cur = queue.poll();
                if (cur != null) {
                    list.add(cur.val);
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } 
                else {
                    list.add(null);
                }
            }
            int i = 0;
            int j = list.size() - 1;
            while (i < j) {
                if (list.get(i++) != list.get(j--)) {
                    return false;
                }
            }
        }
        return true;
    }
}

理解了上述解题思路后，可以来做几道相似的题练习：

1.2 相同的树(LeetCode 100)

【题目链接】100. 相同的树 - 力扣（LeetCode）

1.2.1 思路分析🎯

这道题与对称二叉树很像，但比较对象从单棵树转为了两棵树，所以在比较时不在依次比较左右内外侧节点，而是比较每一个节点(左与左比，右与右比)

1.2.2 代码示例🌰

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        }
        else if (p != null && q == null) {
            return false;
        }
        else if (p == null && q == null) {
            return true;
        }
        else if (p.val != q.val) {
            return false;
        }
        boolean leftFlag = isSameTree(p.left, q.left);
        boolean rightFlag = isSameTree(p.right, q.right);
        return leftFlag && rightFlag;
    }
}

1.3 另一棵树的子树(LeetCode 572)

【题目链接】572. 另一棵树的子树 - 力扣（LeetCode）

1.3.1 思路分析🎯

这道题可以使用 层序遍历 + 判断相同的树(与上道题基本一致) 的方式解决，通过层序遍历找到与子树根节点相同的节点，之后传入这两个节点判断是否构成相同的树

1.3.2 代码示例🌰

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode cur = queue.poll();
                if (cur.val == subRoot.val) {
                    if (isSameTree(cur, subRoot)) {
                        return true;
                    }
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return false;
    }

    boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        }
        else if (p != null && q == null) {
            return false;
        }
        else if (p == null && q == null) {
            return true;
        }
        else if (p.val != q.val) {
            return false;
        }
        boolean leftFlag = isSameTree(p.left, q.left);
        boolean rightFlag = isSameTree(p.right, q.right);
        return leftFlag && rightFlag;
    }
}

2. 翻转二叉树

【题目链接】226. 翻转二叉树 - 力扣（LeetCode）

2.1 思路分析🎯

这里通过层序遍历找到每一个节点，并对该节点的左右节点进行翻转，翻转完后，再将当前节点的左右节点添加进队列中，用于开启下一层的遍历，并重复上述过程，直到每个节点都遍历完 ，返回根节点

2.2 代码示例🌰

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode cur = queue.poll();
                swap(cur);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }

    void swap(TreeNode node) {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

以上便是关于翻转&对称二叉树问题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨