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

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

文章目录

【算法系列-二叉树】对称&翻转二叉树
- 1. 对称二叉树
- - 1.1 思路分析
  - 1.2 相同的树(LeetCode 100)
  - - 1.2.1 思路分析🎯
    - 1.2.2 代码示例🌰
  - 1.3 另一棵树的子树(LeetCode 572)
  - - 1.3.1 思路分析🎯
    - 1.3.2 代码示例🌰
- 2. 翻转二叉树
- - 2.1 思路分析🎯
  - 2.2 代码示例🌰

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;}
}