二叉树
结构定义
1
2
3
4
5
|
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
|
1
2
3
4
5
6
7
8
|
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
|
二叉树的遍历
使用队列进行层序遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def levelorder(root: TreeNode, res: List[List[int]]) -> None:
if root is None: return
q = deque([root])
while q:
n = len(q)
res.append([])
for _ in range(n):
node = q.popleft()
res[-1].append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void levelorder(TreeNode *root, vector<vector<int>> &res) {
if (!root) return ;
queue<TreeNode*> q; q.emplace(root);
while (!q.empty()) {
int n = q.size();
res.emplace_back();
for (int i = 0; i < n; ++i) {
auto node = q.front(); q.pop();
res.back().emplace_back(node->val);
if (node->left) q.emplace(node->left);
if (node->right) q.emplace(node->right);
}
}
}
|
先序遍历：父结点–>左孩子–>右孩子
中序遍历：左孩子–>父结点–>右孩子
后序遍历：左孩子–>右孩子–>父结点
递归
先序遍历
1
2
3
4
5
|
def preorder(root: TreeNode, res: List[int]) -> None:
if root is None: return
res.append(root.val)
preorder(root.left, res)
preorder(root.right, res)
|
1
2
3
4
5
6
|
void preorder(TreeNode *root, vector<int> &res) {
if (!root) return ;
res.emplace_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
|
中序遍历
1
2
3
4
5
|
def inorder(root: TreeNode, res: List[int]) -> None:
if root is None: return
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
|
1
2
3
4
5
6
|
void inorder(TreeNode *root, vector<int> &res) {
if (!root) return ;
inorder(root->left, res);
res.emplace_back(root->val);
inorder(root->right, res);
}
|
后序遍历
1
2
3
4
5
|
def postorder(root: TreeNode, res: List[int]) -> None:
if root is None: return
postorder(root.left, res)
postorder(root.right, res)
res.append(root.val)
|
1
2
3
4
5
6
|
void postorder(TreeNode *root, vector<int> &res) {
if (!root) return ;
postorder(root->left, res);
postorder(root->right, res);
res.emplace_back(root->val);
}
|
非递归
先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def preorder(root: TreeNode, res: List[int]) -> None:
s = [[1, root]]
while s:
p = s[-1]
if p[1] is None:
s.pop()
continue
if p[0] == 1:
p[0] = 2
res.append(p[1].val)
elif p[0] == 2:
p[0] = 3
s.append([1, p[1].left])
else:
s.pop()
s.append([1, p[1].right])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void preorder(TreeNode *root, vector<int> &res) {
stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));
while (!s.empty()) {
auto &p = s.top();
if (!p.second) {
s.pop();
continue;
}
if (p.first == 1) {
p.first = 2;
res.emplace_back(p.second->val);
} else if (p.first == 2) {
p.first = 3;
s.emplace(make_pair(1, p.second->left));
} else {
s.pop();
s.emplace(make_pair(1, p.second->right));
}
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def inorder(root: TreeNode, res: List[int]) -> None:
s = [[1, root]]
while s:
p = s[-1]
if p[1] is None:
s.pop()
continue
if p[0] == 1:
p[0] = 2
s.append([1, p[1].left])
elif p[0] == 2:
p[0] = 3
res.append(p[1].val)
else:
s.pop()
s.append([1, p[1].right])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void inorder(TreeNode *root, vector<int> &res) {
stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));
while(!s.empty()) {
auto &p = s.top();
if (!p.second) {
s.pop();
continue;
}
if (p.first == 1) {
p.first = 2;
s.emplace(make_pair(1, p.second->left));
} else if (p.first == 2) {
p.first = 3;
res.emplace_back(p.second->val);
} else {
s.pop();
s.emplace(make_pair(1, p.second->right));
}
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def postorder(root: TreeNode, res: List[int]) -> None:
s = [[1, root]]
while s:
p = s[-1]
if p[1] is None:
s.pop()
continue
if p[0] == 1:
p[0] = 2
s.append([1, p[1].left])
elif p[0] == 2:
p[0] = 3
s.append([1, p[1].right])
else:
s.pop()
res.append(p[1].val)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void postorder(TreeNode *root, vector<int> &res) {
stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));
while (!s.empty()) {
auto &p = s.top();
if (!p.second) {
s.pop();
continue;
}
if (p.first == 1) {
p.first = 2;
s.emplace(make_pair(1, p.second->left));
} else if (p.first == 2) {
p.first = 3;
s.emplace(make_pair(1, p.second->right));
} else {
s.pop();
res.emplace_back(p.second->val);
}
}
}
|
先序和后序更简单的非递归写法
先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def preorder(root: TreeNode, res: List[int]) -> None:
if root is None: return
s = [root]
while s:
node = s[-1]
res.append(node.val)
s.pop()
if node.right:
s.append(node.right)
if node.left:
s.append(node.left)
|
1
2
3
4
5
6
7
8
9
10
11
|
void preorder(TreeNode *root, vector<int> &res) {
if (!root) return ;
stack<TreeNode*> s; s.emplace(root);
while (!s.empty()) {
auto node = s.top(); s.pop();
res.emplace_back(node->val);
if (node->right) s.emplace(node->right);
if (node->left) s.emplace(node->left);
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def postorder(root: TreeNode, res: List[int]) -> None:
if root is None: return
s = [root]
while s:
node = s[-1]
res.append(node.val)
s.pop()
if node.left:
s.append(node.left)
if node.right:
s.append(node.right)
res[:] = res[::-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void postorder(TreeNode *root, vector<int> &res) {
if (!root) return ;
stack<TreeNode*> s; s.emplace(root);
while (!s.empty()) {
auto node = s.top(); s.pop();
res.emplace_back(node->val);
if (node->left) s.emplace(node->left);
if (node->right) s.emplace(node->right);
}
reverse(res.begin(), res.end());
}
|
平衡二叉树
在平衡二叉树中每个结点的左右两个子树的高度差的绝对值不超过 1。
平衡二叉树判断
自顶向下
$\mathcal{O}(n^2)$
1
2
3
4
5
6
7
8
|
class Solution:
def height(self, root: TreeNode) -> int:
if root is None: return 0
return 1 + max(self.height(root.left), self.height(root.right))
def isBalanced(self, root: TreeNode) -> bool:
if root is None: return True
return abs(self.height(root.left) - self.height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
int height(TreeNode *root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
};
|
自底向上
$\mathcal{O}(n)$
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def height(root: TreeNode) -> int:
if root is None: return 0
left = height(root.left)
right = height(root.right)
if left == -1 or right == -1 or abs(left - right) > 1: return -1
return 1 + max(left, right)
return height(root) != -1
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int height(TreeNode *root) {
if (!root) return 0;
auto left = height(root->left), right = height(root->right);
if (left == -1 || right == -1 || abs(left - right) > 1) return -1;
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
};
|
翻转二叉树
自顶向下
1
2
3
4
5
6
7
|
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None: return root
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
|
1
2
3
4
5
6
7
8
9
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return root;
swap(root->left, root->right);
invertTree(root->left), invertTree(root->right);
return root;
}
};
|
自底向上
1
2
3
4
5
6
7
|
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None: return root
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
return root
|
1
2
3
4
5
6
7
8
9
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return root;
auto left = invertTree(root->left), right = invertTree(root->right);
root->left = right, root->right = left;
return root;
}
};
|