LeetCode 101. 对称二叉树

2020-05-05 16:03:15来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:java抽象类

下一篇:LeetCode 面试题28. 对称的二叉树