LeetCode 101. 对称二叉树

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 101. 对称二叉树

题目

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树?[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

进阶：

• 你可以运用递归和迭代两种方法解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1-镜像递归校验值

步骤：

1. 先验根节点，然后从左右节点开始镜像递归；
2. 也可以从根开始，但其实进行了两次校验（镜像的），没有必要，因为根必然镜像；

算法复杂度:

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

算法源码示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年1月10日 下午10:39:22 
 * @Description: 101. 对称二叉树
 *
 */
public class LeetCode_0101 {

}

// Definition for a binary tree node.
class TreeNode_0101 {
	int val;
	TreeNode_0101 left;
	TreeNode_0101 right;

	TreeNode_0101(int x) {
		val = x;
	}
}

class Solution_0101 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月4日 下午11:34:28 
	 * @param: @param root
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-递归校验；
	 *
	 */
	public boolean isSymmetric(TreeNode_0101 root) {
		if (root == null) {
			return true;
		} else {
			return checkTree(root.left, root.right);
		}
	}

	private boolean checkTree(TreeNode_0101 left, TreeNode_0101 right) {
		// 左右均不为null，且值也相等时继续递归，注意递归的镜像参数
		if (left != null && right != null && left.val == right.val) {
			return checkTree(left.right, right.left) && checkTree(left.left, right.right);
			// 左右均为null时，返回true，该层递归结束
		} else if (left == null && right == null) {
			return true;
			// 左右一个为null一个不为null或左右值不等时，返回false，该层递归结束
		} else {
			return false;
		}
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12832593.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有