原题链接:http://oj.leetcode.com/problems/symmetric-tree/这道题是树的题目,本质上还是树的遍历。这里无所谓哪种遍历方式,只需要对相应结点进行比较即可。一颗树对称其实就是看左右子树是否对称,一句话就是左同右,右同左,结点是对称的相等。题目中也要求了递归和非递归的解法,关于这个我们已经介绍过很多次了,不了解的朋友可以看看Binary
Tree Inorder Traversal,里面介绍了几种树的遍历方式。这道题目也就是里面的程序框架加上对称性质的判断即可。遍历这里就不多说了,我们主要说说结束条件,假设到了某一结点,不对称的条件有以下三个:(1)左边为空而右边不为空;(2)左边不为空而右边为空;(3)左边值不等于右边值。根据这几个条件在遍历时进行判断即可。算法的时间复杂度是树的遍历O(n),空间复杂度同样与树遍历相同是O(logn)。递归方法的代码如下:public boolean isSymmetric(TreeNode root) {
if(root == null)
return true;
return helper(root.left, root.right);
}
public boolean helper(TreeNode root1, TreeNode root2)
{
if(root1 == null && root2 == null)
return true;
if(root1 == null || root2 == null)
return false;
if(root1.val != root2.val)
return false;
return helper(root1.left,root2.right) && helper(root1.right,root2.left);
}
非递归方法仍然是用栈来模拟递归过程,代码如下:public boolean isSymmetric(TreeNode root) {
if(root == null)
return true;
if(root.left == null && root.right == null)
return true;
if(root.left == null || root.right == null)
return false;
LinkedList<TreeNode> q1 = new LinkedList<TreeNode>();
LinkedList<TreeNode> q2 = new LinkedList<TreeNode>();
q1.add(root.left);
q2.add(root.right);
while(!q1.isEmpty() && !q2.isEmpty())
{
TreeNode n1 = q1.poll();
TreeNode n2 = q2.poll();
if(n1.val != n2.val)
return false;
if(n1.left == null && n2.right != null || n1.left != null && n2.right == null)
return false;
if(n1.right == null && n2.left != null || n1.right != null && n2.left == null)
return false;
if(n1.left != null && n2.right != null)
{
q1.add(n1.left);
q2.add(n2.right);
}
if(n1.right != null && n2.left != null)
{
q1.add(n1.right);
q2.add(n2.left);
}
}
return true;
}
从上面可以看出非递归方法比起递归方法要繁琐一些,因为递归可以根据当前状态(比如两个都为空)直接放回true,而非递归则需要对false的情况一一判断,不能如递归那样简练。
分享到:
相关推荐
101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-...
树节点LeetCode---对称树 给定一棵二叉树,检查它是否是自身的镜像(即围绕其中心对称)。 例如,这个二叉树是对称的: 1 / 2 2 / \ / 3 4 4 3 但以下不是: 1 / 2 2 \ 3 3 /** 二叉树节点的定义。 结构树节点{ int ...
LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于佛系,刷刷题吧...
Symmetric tree - Java Recursive - Java Iterative - C Recursive - Python Iterative 0102 Binary Tree Level Order Traversal - Python3 iterative 0103 Binary Tree Zigzag Level Order Traversal - ...
* [Tree](https://github.com/kamyu104/LeetCode#tree) * [Hash Table](https://github.com/kamyu104/LeetCode#hash-table) * [Data Structure](https://github.com/kamyu104/LeetCode#data-structure) * [Math]...
lru缓存leetcode ...https://leetcode.com/problems/symmetric-tree/ Symmetric Tree 102 https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 ...
leetcode 树节点leetcode 测试 仅使用适用于python 方便本地测试,ListNode和TreeNode类型 # filename leetcode.py from leetcode_test ...isSymmetric(self, ...symmetric(left, ...tree = TreeNode.create
leetcode-我的解决方案 我对简单和中等挑战的解决方案 算法和示例 递归 递归是一种程序流程,其中函数调用自身。 递归通常用作回溯搜索方法(DFS)和树计算的技术。 示例:对称树 /** * Definition for a binary ...
leetcode分发糖果 Leetcode C++ Solution Don't try to understand it, feel ...21-合并两个有序链表:merge-two-sorted-lists 83-删除排序链表中的重复元素:remove-duplicates-from-sorted-...101-对称二叉树:symmetric-
Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct ...
对称的二叉树(递归,清晰图解)# Definition for a binary tree node.def isSymmetric(self, root: T