Skip to content

Commit 8422a86

Browse files
JerringJerring
authored
Merge pull request gzc426#9 from gzc426/master
merge
2 parents b2300cd + 9c8e491 commit 8422a86

File tree

27 files changed

+810
-20
lines changed

27 files changed

+810
-20
lines changed

‎2018.11.27-leetcode125/。。。.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
```
12
public boolean isPalindrome(String s){
23
if (s.length() >= 2){
34
int left = 0,right = s.length()-1;
@@ -26,3 +27,4 @@ public boolean isPalindrome(String s){
2627
}
2728
return true;
2829
}
30+
```

‎2018.11.28-leetcode151/。。。.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
```
12
public String reverseWords(String s) {
23
int i = s.length()-1,wordRight=-1;
34
StringBuilder builder = new StringBuilder();
@@ -25,3 +26,4 @@ public String reverseWords(String s) {
2526
}
2627
return builder.toString();
2728
}
29+
```

‎2018.11.29-leetcode443/。。。.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
public int compress(char[] chars) {
1+
```
2+
public int compress(char[] chars) {
23
int cur = 1;//压缩后字符串的长度
34
int repet = 1;
45
for (int i = 1; i < chars.length; i++){
@@ -24,3 +25,4 @@
2425
Log.d(new String(chars));
2526
return cur;
2627
}
28+
```

‎2018.12.04-leetcode101/101. 对称二叉树

Lines changed: 0 additions & 19 deletions
This file was deleted.

‎2018.12.04-leetcode101/Be a fresh man.md

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
## 101_(对称二叉树)Symmetric Tree
2+
## 1 问题描述、输入输出与样例
3+
### 1.1 问题描述
4+
给定一个二叉树，检查它是否是镜像对称的。
5+
### 1.2 输入与输出
6+
输入：
7+
* TreeNode* root：二叉树的根节点指针
8+
9+
输出：
10+
* bool：是否是对称二叉树
11+
12+
### 1.3 样例
13+
#### 1.3.1 样例1
14+
输入: 给定二叉树: [1,2,2,3,4,4,3] ,
15+
16+
1
17+
/ \
18+
2 2
19+
/ \ / \
20+
3 4 4 3
21+
输出: true
22+
23+
#### 1.3.2 样例2
24+
输入:给定二叉树: [1,2,2,null,3,null,3] ,
25+
26+
1
27+
/ \
28+
2 2
29+
\ \
30+
3 3
31+
输出: false<br>
32+
## 2 思路描述与代码
33+
### 2.1 思路描述（队列法）
34+
利用队列做判断
35+
```cpp
36+
根节点左右孩子入队;
37+
while( 队列非空 ){
38+
取出队列两个元素 tmp1, tmp2;
39+
//如果当前节点都是空节点，结束本次循环，即不需要检查后续节点
40+
if(tmp1 == null && tmp2 == null) continue;
41+
//如果不对称，则返回false
42+
if((tmp1 == nullptr && tmp2) || (tmp2 == nullptr && tmp1) || (tmp1->val != tmp2->val))
43+
return false;
44+
//剩下的可能情况就是左右非空且当前节点的值相等，即对称
45+
//然后对这两个节点的左右孩子节点对称入队，保持对称性
46+
//对称入队
47+
tmp1 左孩子入队;
48+
tmp2 右孩子入队;
49+
tmp1 右孩子入队;
50+
tmp2 左孩子入队;
51+
}
52+
return true;
53+
```
54+
55+
### 2.2 代码
56+
```cpp
57+
bool isSymmetric(TreeNode* root) {
58+
if(root == nullptr)
59+
return true;
60+
//使用队列做遍历，这是也可以使用堆栈
61+
queue<TreeNode*> q;
62+
//根节点就不用判断了，直接加入左右孩子节点
63+
q.push(root->left);
64+
q.push(root->right);
65+
while( !q.empty() ){
66+
//从队列弹出两个节点
67+
TreeNode* tmp1 = q.front();
68+
q.pop();
69+
TreeNode* tmp2 = q.front();
70+
q.pop();
71+
//如果都是根节点，则结束本次循环
72+
if(tmp1 == nullptr && tmp2 == nullptr)
73+
continue;
74+
//如果不对称，则返回false
75+
if((tmp1 == nullptr && tmp2) || (tmp2 == nullptr && tmp1) || (tmp1->val != tmp2->val))
76+
return false;
77+
//对称入队
78+
q.push(tmp1->left);
79+
q.push(tmp2->right);
80+
q.push(tmp1->right);
81+
q.push(tmp2->left);
82+
}
83+
//都是对称的，返回真
84+
return true;
85+
}
86+
87+
```
88+
## 3 思考与拓展
89+
### 3.1 思考
90+
本题，利用队列和堆栈做遍历都可以解决这个问题。
91+
#### 3.1.1 其他方法
92+
#### 3.1.1.1 递归法
93+
一棵对称的二叉树必然是左右孩子相等且左右孩子也都是一棵对称的二叉树，利用该思路做递归就行了，这里就不继续写代码了。
94+
#### 3.1.2 复杂度分析
95+
方法|空间复杂度|时间复杂度
96+
--- | --- | ---
97+
队列法|O(2^h),h是树的高度|O(n)
98+
递归法|O(n)|O(n)
99+
#### 3.1.3 难点分析
100+
1. 对称与非对称的判断
101+
102+
### 3.2 拓展
103+
如果让你判断是不是同构的呢？

‎2018.12.04-leetcode101/Istoryforever.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
leetcode of 101
2+
```
3+
/**
4+
* Definition for a binary tree node.
5+
* struct TreeNode {
6+
* int val;
7+
* TreeNode *left;
8+
* TreeNode *right;
9+
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10+
* };
11+
*/
12+
class Solution {
13+
public:
14+
bool isSymmetric(TreeNode* p1,TreeNode * p2){
15+
if((p1 == nullptr && p2!=nullptr) || (p2 == nullptr && p1!=nullptr)) return false;
16+
if(p1 == nullptr && p2 == nullptr) return true;
17+
if(p1->val != p2->val) return false;
18+
return isSymmetric(p1->left,p2->right) && isSymmetric(p1->right,p2->left);
19+
20+
}
21+
bool isSymmetric(TreeNode* root) {
22+
return isSymmetric(root,root);
23+
}
24+
};
25+
```

‎2018.12.04-leetcode101/sourcema.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# LeetCode 101
2+
/**
3+
* Definition for a binary tree node.
4+
* public class TreeNode {
5+
* int val;
6+
* TreeNode left;
7+
* TreeNode right;
8+
* TreeNode(int x) { val = x; }
9+
* }
10+
*/
11+
class Solution {
12+
public boolean isSymmetric(TreeNode root) {
13+
if (root == null) {
14+
return true;
15+
}
16+
return symmetric(root.left, root.right);
17+
}
18+
private boolean symmetric(TreeNode p, TreeNode q) {
19+
if (p == null && q == null) {
20+
return true;
21+
}
22+
if ((p == null && q != null) || (p != null && q == null) || p.val != q.val) {
23+
return false;
24+
}
25+
return symmetric(p.left, q.right) && symmetric(p.right, q.left);
26+
}
27+
}

‎2018.12.04-leetcode101/啦啦啦.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
```java
2+
/**
3+
* Definition for a binary tree node.
4+
* public class TreeNode {
5+
* int val;
6+
* TreeNode left;
7+
* TreeNode right;
8+
* TreeNode(int x) { val = x; }
9+
* }
10+
*/
11+
class Solution {
12+
public boolean isSymmetric(TreeNode root) {
13+
return cal(root,root);
14+
}
15+
16+
boolean cal(TreeNode r1,TreeNode r2){
17+
if(r1==null&&r2==null)return true;
18+
if(r1==null||r2==null)return false;
19+
return r1.val==r2.val&&cal(r1.left,r2.right)&&cal(r1.right,r2.left);
20+
}
21+
}
22+
```

‎2018.12.04-leetcode101/李碧涵.md

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
### [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/description/)
2+
**题目描述**
3+
> 判断是否是镜像二叉树（对称）
4+
5+
**例子**
6+
略
7+
8+
**思想**
9+
（递归）
10+
定义一辅助函数，输入为left和right，判断是否相等。
11+
（迭代）
12+
定义两个栈，层次遍历时判断，并分别从左向右和从右向左存储。
13+
14+
**解法1**
15+
递归
16+
```python
17+
# Definition for a binary tree node.
18+
# class TreeNode(object):
19+
# def __init__(self, x):
20+
# self.val = x
21+
# self.left = None
22+
# self.right = None
23+
24+
class Solution(object):
25+
def isSymmetric(self, root):
26+
"""
27+
:type root: TreeNode
28+
:rtype: bool
29+
"""
30+
if not root:
31+
return True
32+
return self.helper(root.left, root.right)
33+
34+
def helper(self, left, right):
35+
if not left and not right:
36+
return True
37+
if not left or not right or left.val != right.val:
38+
return False
39+
return self.helper(left.left, right.right) and self.helper(left.right, right.left)
40+
```
41+
**解法2**
42+
迭代
43+
```python
44+
# Definition for a binary tree node.
45+
# class TreeNode(object):
46+
# def __init__(self, x):
47+
# self.val = x
48+
# self.left = None
49+
# self.right = None
50+
51+
class Solution(object):
52+
def isSymmetric(self, root):
53+
"""
54+
:type root: TreeNode
55+
:rtype: bool
56+
"""
57+
if not root or not root.left and not root.right:
58+
return True
59+
if not root.left or not root.right:
60+
return False
61+
62+
queue1, queue2 = [root.left], [root.right]
63+
while queue1 and queue2:
64+
node1 = queue1.pop(0)
65+
node2 = queue2.pop(0)
66+
67+
if node1.val != node2.val:
68+
return False
69+
70+
if node1.left and node2.right:
71+
queue1.append(node1.left)
72+
queue2.append(node2.right)
73+
elif node1.left or node2.right:
74+
return False
75+
76+
if node1.right and node2.left:
77+
queue1.append(node1.right)
78+
queue2.append(node2.left)
79+
elif node1.right or node2.left:
80+
return False
81+
return True
82+
```

‎2018.12.04-leetcode101/杨.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
```
2+
/**
3+
* 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
4+
* 如果同时满足下面的条件，两个树互为镜像：
5+
* 1.它们的两个根结点具有相同的值。
6+
* 2.每个树的右子树都与另一个树的左子树镜像对称。
7+
*/
8+
public boolean isSymmetric(TreeNode root) {
9+
if(root == null ){
10+
return true;
11+
}
12+
return isMirrorSymmetry(root.left,root.right);
13+
}
14+
15+
public boolean isMirrorSymmetry(TreeNode left,TreeNode right){
16+
if(left==null && right==null){
17+
return true;
18+
}
19+
if(left==null || right==null){
20+
return false;
21+
}
22+
return left.val==right.val && isMirrorSymmetry(left.left,right.right) && isMirrorSymmetry(left.right,right.left);
23+
}
24+
25+
```

0 commit comments

Comments
 (0)