/**
* Symmetric Tree
*
* Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
* */
public class S101 {
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(2);
n1.left = n2;
n1.right = n3;
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(3);
n2.right = n4;
n3.left = n5;
System.out.println(isSymmetric(n1));
}
public static boolean isSymmetric(TreeNode root) {
// 不用继续比较了
if(root == null){
return true;
}
return isSymmetricRec(root.left, root.right);
}
// 比较一个树是不是对称树比较难写递归,所以改写成比较两个树是否对称树
private static boolean isSymmetricRec(TreeNode t1, TreeNode t2){
// 如果同时为空,则相等
if(t1==null && t2==null){
return true;
}else if(t1==null || t2==null){ // 如果一个空一个不空,则不等
return false;
}
// 根节点的值必须要相等!
if(t1.val != t2.val){
return false;
}
// 原来我这里还这样写,但是这有两个问题,
// 一个是如果Java比较对象,即使里面是同样的值,如果非引用同一对象,则还是不一样!
// 所以要区分是否为null的情况,比较麻烦!
// 另一点是根本没必要做这个比较,因为递归会处理好!
// 总结:只要写base case(没有节点或者只有一个节点)就够了,无需在base case里面
// 处理更复杂的case,更复杂的在下面的return递归里写!
/*
if(t1.left != t2.right || t1.right!=t2.left){
return false;
}
*/
// 对称树的本质
return isSymmetricRec(t1.left, t2.right) && isSymmetricRec(t1.right, t2.left);
}
}
分享到:
相关推荐
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
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 ...
isSymmetric(TreeNode root) { if(root == NULL) return true; return checkSymmetric(root->left, root->right); } bool checkSymmetric(TreeNode* left, TreeNode* right) { if(left == NULL && right == NULL) ...
leetcode 树节点leetcode 测试 仅使用适用于python 方便本地测试,ListNode和TreeNode类型 # filename leetcode.py from leetcode_test ...isSymmetric(self, ...symmetric(left, ...tree = TreeNode.create
leetcode 答案 LeetCode-Trip ...Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]
101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-...
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 - ...
leetcode分发糖果 Leetcode C++ Solution Don't try to understand it, feel ...21-合并两个有序链表:merge-two-sorted-lists 83-删除排序链表中的重复元素:remove-duplicates-from-sorted-...101-对称二叉树:symmetric-
tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param { TreeNode } root * @return { boolean } */ var isSymmetric = function ( root ) { if ( root ...
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