[数据结构与算法]扣初级算法-25-树-对称二叉树

学习目标：

本次学习目标为 力扣初级算法-树，其中主要的LC如下：

• 对称二叉树

学习内容：

1. 验证二叉搜索树 -----（[链接](https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn7ihv/）
   给定一个二叉树，检查它是否是镜像对称的。
   例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
   1
   / \
   2 2
   / \ / \
   3 4 4 3
   但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
   1
   / \
   2 2
   \ \
   3 3

解题思路：

• 解法一： 直接递归

• 解题思路：

  • 判断树是否对称，则需要从子节点开始比较，两个子节点的值必须相同，并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点
  • 边界问题： 根节点是空节点，则返回 true
  • 分析左、右节点的情况，如果两者都是空，则不需要比较，直接return ture
  • 如果两个非都是空，再细分 则要判断两者值，同时还需要判断其子节点，可领出不相等的情况直接返回，因为若相等还需要继续递归往下处理
  • 继续递归子类

• 代码实现：

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

	/**
	 * 直接递归法
	 * 判断树是否对称，则需要从子节点开始比较，两个子节点的值必须相同，并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点
	 */
	public boolean isSymmetric(TreeNode root) {
		// 边界问题： 根节点是空节点，则返回 true
		if (null == root){
			return true;
		}
		return isSymmetricHelper(root.left, root.right);
	}

	private boolean isSymmetricHelper(TreeNode left, TreeNode right) {
		// 分析左、右节点的情况，如果两者都是空，则不需要比较，直接return ture
		if (null == left && null == right){
			return true;
		}

		// 如果两个非都是空，再细分 则要判断两者值，同时还需要判断其子节点，可领出不相等的情况直接返回，因为若相等还需要继续递归往下处理
		if (null == left || null == right || right.val != left.val){
			return false;
		}

		return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
	}