刷题笔记，主题是树，以LeetCode上的题目为例。树相关的题目大多使用到递归的思想， 尤其是在深度优先遍历中；还有一类遍历方式：宽度优先遍历，使用队列来实现。
- ** 判断是不是一个二叉搜索树？**
解题思路有二。一方面是可以递归的进行判断，如果根节点大于（严格）左子树，小于右子树。那么是一个二叉搜索树。另一方可以使用区间的思想。就是下面的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 判断是否是二叉搜索树， 左子树< 根节点< 右子树
// 使用区间的概念，根节点 [INT_MIN, INT_MAX]
bool isValidBST(TreeNode* root) {
return dfs(root, INT_MIN, INT_MAX);
}
bool dfs(TreeNode * root, long long minv, long long maxv)
{
if(!root) return true;
if(root-> val < minv || root->val > maxv) return false;
return dfs(root-> left, minv, root->val- 1ll) && dfs(root-> right, root->val+1ll, maxv);
}
};
|
- ** Binary Tree Inorder Traversal**
中序非递归遍历。
a. 将整个树的最左边一条链压入栈中
b. 每次取出栈顶元素，如果有右子树，那么将右子树压入栈中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode *> stk;
auto p =root;
// 这个条件也是比较nice的， p || stk.size()
while( p || stk.size())
{
while(p )
{
stk.push(p);
p =p-> left;
}
// 这个p 是一个遍历指针，类似i，是可以重复的赋值的
p = stk.top();
stk.pop();
//auto tmp =stk.top();
//stk.pop();
res.push_back(p-> val);
// 然后就转向了右子树
p =p->right;
}
return res;
}
};
|
- Symmetric Tree
递归判断是否是 symmetric tree。 这个还是非常nice的。 这种思路比较简单的，根节点不用比较，然后左右子树，左子树的左结点和右子树的右节点，左子树的右节点和右子树的左结点。
a. 两个根节点的值要相等
b. 左边的左子树和右边的右子树对称
c. 左边的右子树和右边的左子树对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 对称， 左子树的左结点 和右子树的右节点； 左子树的右节点和右子树的左结点
//
bool isSymmetric(TreeNode* root) {
// 如果为空 那么 return true
if (! root) return true;
return dfs(root-> left, root -> right);
}
bool dfs(TreeNode * left, TreeNode * right)
{
if(! left || ! right) return !left && ! right; // 只有两者都为空，那么才是true
if(left-> val != right -> val)
return false;
return dfs(left-> left, right -> right) && dfs(left-> right, right -> left);
}
};
|
- 重建二叉树
根据前序遍历和中序遍历重塑二叉树。
在一个无序的list 中去查找二叉树，时间是 $O(n)$，这个是可以使用hash 优化成 $O(1)$。重点是可以通过长度进行划分 左子树序列和右子树序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, int> hash;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n =preorder.size();
for(int i =0; i< n; i++)
hash[inorder[i]] =i;
return dfs(preorder, inorder, 0, n -1, 0, n -1);
}
TreeNode * dfs(vector<int>& preorder, vector<int> & inorder, int pl, int pr, int il, int ir)
{
// dfs 一定是有return 的
if(pl > pr) return NULL ;
int val =preorder[pl];
int index =hash[val];
int len =index -il;
TreeNode* root =new TreeNode(val);
root -> left =dfs(preorder, inorder, pl+1, pl +len, il, index -1);
root -> right =dfs(preorder, inorder, pl+len+1, pr, index +1, ir);
return root;
}
};
|
- 层序遍历，非递归写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 层次遍历，先进先出，队列的东西
queue<TreeNode *> q;
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
q.push(root);
while(q.size())
{
vector<int> level;
int n = q.size();
// 这个是需要划分成一层的
for(int i =0; i< n; i++)
{
auto tmp =q.front();
q.pop();
level.push_back(tmp->val );
if(tmp -> left) q.push(tmp -> left);
if(tmp -> right) q.push(tmp -> right);
}
res.push_back(level);
}
return res;
}
};
|
- lowest common ancestor of a binary tree
二叉树的最小公共父节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 最短公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(! root || p ==root || q ==root) return root;
// 否则就需要进行寻找
auto left =lowestCommonAncestor(root ->left, p, q);
auto right =lowestCommonAncestor(root -> right, p, q);
if( !left) return right;
if(! right) return left;
return root;
}
};
|
- serialize and deserialize binary tree
一般来说，单独的前序遍历是不能唯一确定一个树的结构。（使用前序遍历和中序遍历才能确定一个二叉树的结构，如之前的题目）但是这里可以唯一确定，因为前序遍历中把空节点加入了整个序列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// 编码的格式 1,2,#,#,
// Encodes a tree to a single string.
// 使用string 的地址表示 exactly 的那种结果
string serialize(TreeNode* root) {
string res;
dfs1(root, res);
return res;
}
void dfs1(TreeNode * root, string & res)
{
if(! root)
{
res +="#,";
return;
}
res += to_string(root->val)+',';
dfs1(root->left, res);
dfs1(root->right, res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u=0 ;
return dfs2(data, u);
}
TreeNode* dfs2(string &data, int & u)
{
if(data[u] =='#')
{
u +=2; // 一个 # 一个,
return NULL ;
}
bool is_minus =false;
if(data[u] =='-')
{
is_minus =true;
u ++;
}
int val =0;
while(data[u] != ',')
{
val = val *10 +data[u] -'0';
u ++;
}
u ++;
if(is_minus) val =-val;
auto root =new TreeNode(val);
root->left =dfs2(data, u);
root ->right =dfs2(data, u);
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
|
- diameter of binary tree
先是枚举节点，然后求解左右子树深度之和。因为左右子树是没有联系的，是可以单独求解左右子树的最大深度。（ 和下一道题目相比，这个所有的权重都是 1) 时间复杂度是 $O(n)$， 因为这个一定是从根节点出发 的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 这个题目和最长路径不一样，在于这个是求解边的长度，而不是结点的个数
// 所以最长的是一定是从根节点出发的， 然后dfs进行
// 长度是 left + right
// 时间复杂度是 O(n)
int res =0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
// 这个不是dfs ，这个是从root向下走的最大的路径
int dfs(TreeNode * root)
{
if( !root) return 0;
auto left =dfs(root -> left);
auto right =dfs( root -> right);
res =max(res, left +right);
return max(left, right) +1;
}
};
|
- binary tree maximum path sum
这个权重有正有负。时间复杂度是 $O( n^2)$， 首先枚举的是点 $O(n)$ ，然后每个点上计算， 那么也是 $O(n)$， 最后的结果是 $O(n ^2)$。
这里实际上是有三种路径的：
a. root -> val + L
b. root->val + R
c. root ->val
所以看一下最后是三种选择的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 权重可以看成 root ->val
int res =INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return res;
}
// 从根节点遍历
int dfs(TreeNode* root)
{
if(! root)
return 0;
// 左右子树的最大值
int left =dfs(root -> left);
int right =dfs(root -> right);
res =max(res, left +right + root ->val);
// 返回当前节点的最大值
return max(0, max(left, right) + root -> val);
}
};
|
173. Binary Search Tree Iterator
其中的 average 是均摊的意思， $O(n) $ 除以 $n$ 那么最后的结果是 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
# 使用过栈 模拟中序遍历的过程， next 表示栈顶元素
def __init__(self, root: TreeNode):
self.stk =[]
while root:
self.stk.append(root)
root =root.left
def next(self) -> int:
"""
@return the next smallest number
"""
popp =self.stk.pop()
root =popp.right
while root:
self.stk.append(root)
root = root.left
return popp.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return self.stk
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
|
919. Complete Binary Tree Inserter
使用了完全二叉树中根节点和叶子节点的性质。空间复杂度是$O(n)$，insert 的时间复杂度是$O(1)$，但是建立层次遍历的结果是$O(n)$，所以总的时间复杂度是$O(n)$。
（注意和下文中的c++实现的对比）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class CBTInserter(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.rootnode =root
self.nodes =[TreeNode(0)] #初始化一个节点，使根节点从数组中序号为1 开始
# 队列一般是bfs，这里得到是一个层次遍历的结果
q =collections.deque([root])
while q:
t =q.popleft()
self.nodes.append(t)
if t.left : q.append(t.left)
if t.right: q.append(t.right)
def insert(self, v):
"""
:type v: int
:rtype: int
"""
node =TreeNode(v)
index =len(self.nodes) //2
self.nodes.append(node)
if not self.nodes[index].left:
self.nodes[index].left =node
else:
self.nodes[index].right =node
return self.nodes[index].val
def get_root(self):
"""
:rtype: TreeNode
"""
return self.rootnode
# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()
|
919. Complete Binary Tree Inserter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// 首先是对于complete tree 的定义，完全二叉树是 和数字序号一一对应。大根堆和小根堆也是一种完全二叉树，当前的i 和左子树是 2*i， 右子树是 (2*i+1)的性质
class CBTInserter {
public:
TreeNode * root;
queue<TreeNode*> q;
CBTInserter(TreeNode* root) {
this->root =root;
q.push(root);
while(true)
{
auto p =q.front();
if (! p->left)
break;
q.push(p->left);
if(! p->right)
break;
q.push(p->right);
q.pop();
}
}
int insert(int v) {
auto p =q.front();
auto new_node =new TreeNode(v);
if( ! p->left) p->left =new_node;
else
{
p->right =new_node;
q.pop(); // 只有末尾两行的结点是可以当做父节点的存在，其他的是不太可能的；
}
q.push(new_node);
return p->val;
}
TreeNode* get_root() {
return root;
}
};
/**
* Your CBTInserter object will be instantiated and called as such:
* CBTInserter* obj = new CBTInserter(root);
* int param_1 = obj->insert(v);
* TreeNode* param_2 = obj->get_root();
*/
|
二叉搜索树的第k个结点
来自剑指offer。二叉搜索树就是二叉排序树。中序遍历是先左子树，根节点，最后是右子树，提供两种写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* res;
TreeNode* kthNode(TreeNode* root, int k) {
if(!root) return res;
dfs(root, k);
return res;
}
void dfs(TreeNode * root, int& k) # 这里可能最重要是使用引用而非值传递
{
if(!root) return ;
dfs(root->left, k);
k -=1;
if(!k) res =root;
if(k>0) dfs(root->right, k);
}
};
|
637. Average of Levels in Binary Tree
先序遍历，先是根节点，然后是左右子树，时间复杂度是$O(n)$。（ 这种做法有点类似层序遍历呀）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *r, int level, vector<double> & ans, vector<int> & counter)
{
if (!r) return ;
if(ans.size() ==level) # 这个语句很好的处理，c++ 中index 访问的问题。
{
ans.push_back(0);
counter.push_back(0);
}
ans[level] += r ->val;
counter[level] ++;
dfs(r -> left, level+1, ans, counter);
dfs(r->right, level +1, ans, counter);
}
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
vector<int> counter;
dfs(root, 0, ans, counter);
for(int i =0; i< ans.size(); i ++)
ans[i] /= counter[i];
return ans;
}
};
|
LeetCode 617. Merge Two Binary Trees
递归的做法。从根节点开始， 分成四种情况，如果两树$t_1$， $t_2$都为空，那么返回为空； 如果$t_1$为空，那么返回$t_2$；如果$t_2$为空，那么返回$t_1$；否则分别递归的左右子树。
因为每个结点最多遍历一次，所以时间复杂度是$O(m+n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 如果对于递归不是很了解，那么就适合去做 树相关的习
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(!t1 && !t2)
return nullptr;
if(!t1 && t2)
return t2;
if(t1 && !t2)
return t1;
t1 -> val += t2->val;
t1 -> left =mergeTrees(t1->left, t2 -> left);
t1 -> right =mergeTrees(t1 -> right, t2 -> right);
return t1;
}
};
|
LeetCode 606. Construct String from Binary Tree
需要注意的是，如果只有在左孩子，无序添加一对括号，如果只有右孩子，那么需要添加一对括号，表示两者之间的一一对应的关系。时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/**
* Definition for a binary tree node.
* struct TreeNode {
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *r, string & s)
{
if(!r)
return nullptr;
s += to_string(r ->val);
if( !r -> left && !r ->right)
return ;
s += '(';
dfs(r ->left, s);
s += ')';
if(r -> right)
{
s += '(';
dfs(r -> right, s);
s += ')';
}
}
string tree2str(TreeNode* t) {
string ans ="";
dfs(t, ans);
return ans;
}
};
|
606. Construct String from Binary Tree
需要注意的是，如果只有在左孩子，无序添加一对括号，如果只有右孩子，那么需要添加一对括号，表示两者之间的一一对应的关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/**
* Definition for a binary tree node.
* struct TreeNode {
int val;
TreeNode * left;
TreeNode * right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *r, string & s)
{
if(!r)
return ;
s += to_string(r ->val);
if( !r -> left && !r ->right)
return ;
s += '(';
dfs(r ->left, s);
s += ')';
if(r -> right)
{
s += '(';
dfs(r -> right, s);
s += ')';
}
}
string tree2str(TreeNode* t) {
string ans ="";
dfs(t, ans);
return ans;
}
};
|
572. Subtree of Another Tree
时间复杂度是$O(mn)$，对于大树 $s$中的每个结点，都是需要在小树 $t$中遍历一遍，所以是两者个数的相乘。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode *s, TreeNode * t)
{
if(!s)
return false;
return isSame(s, t) || dfs(s->left, t) || dfs(s ->right, t);
}
bool isSame(TreeNode *s, TreeNode *t)
{
if(!s && !t)
return true;
if(!s && t || s && !t || s ->val != t->val )
return false;
return isSame(s->left, t ->left) && isSame(s->right, t->right);
}
bool isSubtree(TreeNode* s, TreeNode* t) {
return dfs(s, t);
}
};
|
LeetCode 563. Binary Tree Tilt
看着比较高大上，实际上就是树的遍历问题，可以使用深度遍历的方式。深度优先遍历，时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int dfs(TreeNode *r, int &sum)
{
if(!r) return 0;
int ls =dfs(r ->left, sum);
int rs =dfs(r->right, sum);
sum += abs(ls -rs);
return ls +rs + r->val;
}
int findTilt(TreeNode* root) {
int sum =0;
dfs(root, sum);
return sum;
}
};
|
538. Convert BST to Greater Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 这个是二叉搜索树，左子树小于根节点，根节点小于右子树
// 要求求解累加树，是一个逆中序遍历 （右中左）
// 中序遍历（左子树 根节点 右子树）
void traverse(TreeNode * r, int &sum)
{
// sum 表示一种累加和
if (!r) return ;
traverse(r ->right, sum);
r -> val +=sum;
sum = r->val;
traverse(r ->left, sum);
}
TreeNode* convertBST(TreeNode* root) {
int sum =0;
traverse(root, sum);
return root;
}
};
|
530. Minimum Absolute Difference in BST
需要使用额外的变量 存储上一个结点；大多数的问题都是树的遍历求解问题；如果限定是二叉搜素树，那么很大的可能是中序遍历（因为只有中序遍历结果是递增有序的，所以是很好的性质）
（之前所有的题目都是这样的，都是假设栈的开销不被计算在内，这样才能够分析空间复杂度）
假设由递归产生的隐式调用栈的开销不被计算在内
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *r, int &last, int & ans)
{
if(r ==NULL)
return ;
dfs(r ->left, last, ans);
if(last != -1)
ans =min(ans, r ->val -last);
last =r -> val;
dfs(r ->right, last, ans);
}
int getMinimumDifference(TreeNode* root) {
int last =-1, ans =INT_MAX;
dfs(root, last, ans);
return ans;
}
};
|
112. Path Sum
自顶向下，没经过一个结点，sum减去该结点的数值，只有两条路径，要么是从 left 走，要么是从right 走，最后判断是否满足条件。每个节点仅被遍历一次，时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root ->left && !root ->right) return root -> val == sum;
if(root ->left && hasPathSum(root->left, sum -root->val)) return true;
if(root ->right && hasPathSum(root->right , sum -root->val) ) return true;
return false;
}
};
|
113. Path Sum II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 上一个题目判断是否存在这样的路径，这个题目是返回这样符合条件的路径。
// 时间复杂度，因为判断是否存在，只是需要找到一条路径即可；而找到所有的路径需要的时间复杂度是$O(n^2)$
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(! root) return ans;
dfs(root, sum);
return ans;
}
void dfs(TreeNode* root, int sum)
{
path.push_back(root->val);
sum -= root->val;
if(root ->left || root ->right)
{
if(root ->left) dfs(root ->left, sum);
if(root ->right) dfs(root ->right, sum);
}
else
{
if(!sum)
ans.push_back(path);
}
path.pop_back();
}
};
|
404. Sum of Left Leaves
（这个数字是非常的吉利呀）， 使用 left 来标识是否是左右子树，非常的nice。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sum ;
int sumOfLeftLeaves(TreeNode* root) {
dfs(root, false);
return sum;
}
void dfs(TreeNode * root, bool left)
{
if (!root) return ;
if(left && !root ->left && !root ->right)
sum += root ->val;
dfs(root ->left, true);
dfs(root ->right, false);
}
};
|
993. Cousins in Binary Tree
通过树的遍历，分别找到 x 和 y 的深度和对应的父节点，可以采用深度优先或者宽度优先的方式。时间复杂度是$O(n)$， 如果是深度优先遍历，那么是需要$O(h)$的栈空间，如果是宽度优先遍历，需要$O(n)$ 的队列空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *rt, TreeNode *fa, int x, int depth, int &d, TreeNode * &f)
{
if(rt -> val ==x)
{
d =depth;
f =fa;
return ;
}
if(rt ->left != nullptr)
dfs(rt ->left, rt, x, depth +1, d, f);
if(d ==-1)
{
if(rt -> right != nullptr)
dfs(rt ->right, rt , x, depth +1, d, f);
}
}
bool isCousins(TreeNode* root, int x, int y) {
int dx =-1, dy =-1;
TreeNode *fx, *fy;
// 总的思路还是分别求解出 x y 的深度和头结点
dfs(root, nullptr, x, 0, dx, fx);
dfs(root, nullptr, y, 0, dy, fy);
if(dx != dy)
return false;
return fx != fy;
}
};
|
965. Univalued Binary Tree
这个题目判断树中的值是否全部都是一样的，就是树的遍历问题，可以使用深度优先或者宽度优先。时间复杂度是$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool check(TreeNode *r, int val)
{
if (!r) return true;
if(r ->val != val)
return false;
return check(r ->left, val) && check(r ->right, val);
}
bool isUnivalTree(TreeNode* root) {
// 判断是否具有唯一值,
int val =root ->val;
return check(root, val);
}
};
|
LeetCode 559. Maximum Depth of N-ary Tree
对于n 叉树的遍历，返回其最大的深度。时间复杂度是$O(n)$。对于树的题目，除了比较经典的二叉树结构之外，还需要掌握多叉树的结构。二叉搜索树的相关题目也是很多呀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int dfs(Node *r)
{
if(!r) return 0;
int d =1;
// 就是在叶子结点中最大的深度
for(auto ch : r ->children)
d = max(d, dfs(ch) +1);
return d;
}
int maxDepth(Node* root) {
return dfs(root);
}
};
|
LeetCode 669. Trim a Binary Search Tree
递归在逻辑上是比较简单的，二叉搜索树因为具有排序的性质，所以是经常的考点。时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if(!root) return root;
if(root -> val < L)
return trimBST(root-> right, L, R);
else if(root ->val > R)
return trimBST(root ->left, L, R);
root -> left = trimBST(root -> left, L, R);
root -> right = trimBST(root -> right, L, R);
return root;
}
};
|
1305. All Elements in Two Binary Search Trees
时间复杂度$O(m +n)$， 空间复杂度： 递归的系统栈最坏情况下需要$O(m+n)$空间，中间的数组也是$O(m+n)$，所以总的空间复杂度是$O(m +n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 这个思路很简单
void traverse(TreeNode * r, vector<int> & s)
{
if(!r) return ;
traverse(r->left, s);
s.push_back(r ->val);
traverse(r->right, s);
}
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int> s1, s2, res;
traverse(root1, s1);
traverse(root2, s2);
int i =0, j =0;
// 这种写法 非常的nice，将归并的做法合在了一起
while(i < s1.size() || j < s2.size())
{
if(j ==s2.size())
res.push_back(s1[i++]);
else if (i ==s1.size())
res.push_back(s2[j++]);
else
{
if(s1[i] < s2[j])
res.push_back(s1[i++]);
else
res.push_back(s2[j++]);
}
}
return res;
}
};
|
NAC
LeetCode 501. Find Mode in Binary Search Tree
在遍历的过程中，加上一个统计工作，之前在数组中找众数也是这个逻辑，只不过遍历的方式不一样了。
在分析空间复杂度的时候，除了记录答案的额数组和递归使用的系统栈外，其余只使用了常数的内存空间 这样的描述是相当的精确。
题目中对于BST 进行了重新的定义，小于等于也是算作左子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *r, vector<int>& ans, int& last_num, int& num_count, int& ans_count) {
if (r == NULL)
return;
dfs(r -> left, ans, last_num, num_count, ans_count);
if (r -> val != last_num) {
if (num_count > ans_count) {
ans_count = num_count;
ans.clear();
ans.push_back(last_num);
}
else if (num_count == ans_count) {
ans.push_back(last_num);
}
last_num = r -> val;
num_count = 1;
}
else {
num_count++;
}
dfs(r -> right, ans, last_num, num_count, ans_count);
}
vector<int> findMode(TreeNode* root) {
vector<int> ans;
int last_num = -1, num_count = -1, ans_count = 0;
dfs(root, ans, last_num, num_count, ans_count);
if (num_count > ans_count) {
ans_count = num_count;
ans.clear();
ans.push_back(last_num);
}
else if (num_count == ans_count) {
ans.push_back(last_num);
}
return ans;
}
};
|
938. Range Sum of BST
通过二叉搜索树 的性质判断 某个结点是否在左右子树之间。递归遍历，时间复杂度是$O(n)$，空间复杂度有一个系统的栈空间$o(k)$，除此之外是$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode * rt, int L, int R, int & ans)
{
if( !rt ) return ;
if(L <= rt ->val && rt ->val <= R)
ans += rt ->val;
if(L < rt ->val)
dfs(rt->left, L, R, ans);
if(rt ->val < R)
dfs(rt->right, L, R, ans);
}
int rangeSumBST(TreeNode* root, int L, int R) {
int ans =0;
dfs(root, L, R, ans);
return ans;
}
};
|
671. Second Minimum Node In a Binary Tree
寻找第二小的值，由题目知道根节点的数字是最小的，那么就需要递归寻找其左右子树中最小的树，注意只有当前节点的值和根节点的值相等的情况下，才可能进行递归。
···c++
/**
- Definition for a binary tree node.
- struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- };
*/
class Solution {
public:
void find(TreeNode r, int minr, int &ans)
{
if(!r) return ;
if(r->val != minr )
{
if(ans ==-1)
ans = r ->val;
else
ans = min(ans, r ->val);
return ;
}
// 进行dfs 操作的是这里，如果和根节点相同的话，那么就递归其左右子树了
find(r ->left, minr, ans);
find(r->right, minr , ans);
}
int findSecondMinimumValue(TreeNode root) {
int ans =-1;
find(root, root->val, ans);
return ans;
}
};
···
872. Leaf-Similar Trees
不管是dfs 还是bfs，每个节点都是要遍历的，只是在选择的是不一样；时间复杂度分析，需要遍历两颗树的节点，时间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode * root, vector<int> & path)
{
if(!root) return ;
if(root ->left) dfs(root->left, path);
if(root ->right) dfs(root ->right, path);
if(! root ->left && ! root->right) path.push_back(root ->val);
}
// 这个就是遍历叶子节点
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> seq1, seq2;
dfs(root1, seq1);
dfs(root2, seq2);
if(seq1.size() != seq2.size())
return false;
for(int i =0; i< seq1.size() ; i++)
if(seq1[i] != seq2[i])
return false;
return true;
}
};
|
Postorder 后序遍历，后根遍历。
590. N-ary Tree Postorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
// 迭代法后序遍历， n叉树
vector<int> postorder(Node* root) {
vector<int> ans;
if(!root) return ans;
stack<pair<Node* ,int>> st;
st.push(make_pair(root, 0));
while(!st.empty())
{
auto cur = st.top();
st.pop();
if(cur.second < cur.first -> children.size() )
{
st.push(make_pair(cur.first, cur.second +1));
st.push(make_pair(cur.first->children[cur.second], 0));
}
else
ans.push_back(cur.first ->val);
}
return ans;
}
};
|
589. N-ary Tree Preorder Traversal
要求使用迭代法实现树的遍历，使用栈的数据结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<int> preorder(Node* root) {
vector<int> ans;
if(!root) return ans;
stack<pair<Node*, int>> st;
st.push(make_pair(root, 0));
while(!st.empty())
{
auto cur =st.top();
st.pop();
if(cur.second ==0)
ans.push_back(cur.first ->val);
if(cur.second < cur.first -> children.size())
{
st.push(make_pair(cur.first, cur.second +1));
st.push(make_pair(cur.first -> children[cur.second], 0));
}
}
return ans;
}
};
|
897. Increasing Order Search Tree
时间复杂度是$O(n)$， 需要系统提供栈空间，大小为树的深度，故空间复杂度是$O(H)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* solve(TreeNode * &rt)
{
if(rt ->left ==nullptr && rt->right ==nullptr )
return rt;
if(rt ->left ==nullptr && rt ->right != nullptr)
return solve(rt->right);
TreeNode *right_most =solve(rt ->left);
TreeNode * left =rt ->left;
right_most -> right =rt;
rt ->left = nullptr;
rt =left;
return solve(right_most ->right);
}
TreeNode* increasingBST(TreeNode* root) {
solve(root);
return root;
}
};
|
medium 类型的题目
654. Maximum Binary Tree
选择当前list 中的最大值为根节点，然后左边的为左子树；右边为右子树; 递归进行。时间复杂度，当数组是有序的，那么每次分别需要 n n-1 n-2 … 1 次数进行计算， 所以最后的时间复杂度是$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode * build(const vector<int> & nums, int l, int r)
{
if(l >r) return nullptr;
int max_num = nums[l], max_i =l;
for(int i =l +1; i<= r; i++)
if( max_num < nums[i])
{
max_num=nums[i];
max_i =i;
}
TreeNode *rt =new TreeNode(max_num);
rt ->left = build(nums, l, max_i -1);
rt ->right =build(nums, max_i +1, r);
return rt;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return build(nums, 0, nums.size() -1);
}
};
|
96. Unique Binary Search Trees
动态规划 时间复杂度$O(n^2)$， $f[n]$ 表示 $n$个节点的二叉搜索树共有多少种。状态转移表示为如下形式：
\begin{equation}
f[n]=\sum_{k=0}^{n-1} f[k] * f[n-1-k]
\end{equation}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int numTrees(int n) {
vector<int> f(n+1);
f[0] =1;
for(int i =1; i<=n; i++)
{
f[i] =0;
for(int j =1; j<= i; j++)
f[i] += f[j-1] * f[i-j];
}
return f[n];
}
};
|