二叉树遍历
相关题目：
翻转⼆叉树（简单）
⼆叉树展开为链表（中等）
填充每个节点的下⼀个右侧节点指针（中等）
二叉树递归：明确函数的定义，根据定义递归推导最终结果。先搞清楚当前根节点”该做什么”与”什么时候做”，然后根据函数定义递归调⽤⼦节点，让孩⼦节点做相同的事情。
翻转二叉树
输⼊⼀个⼆叉树根节点 root，把整棵树镜像翻转，⼆叉树上的每⼀个节点的左右⼦节点进⾏交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* tmp = root -> left;
root -> left = root -> right;
root -> right = tmp;
invertTree(root -> left);
invertTree(root -> right);
return root;
}
|
填充⼆叉树节点的右侧指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
1
2
3
4
5
6
| struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
|
⼆叉树的问题难点在于，如何把题⽬的要求细化成每个节点需要做的事情，如果只依赖一个节点进行递归，无法连接跨父节点的两个相邻节点。需细化为两个节点进行递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
Node* connect(Node* root) {
if (root == nullptr) return nullptr;
connectTwoNode(root -> left, root -> right);
return root;
}
void connectTwoNode(Node* node1, Node* node2) {
if (node1 == nullptr || node2 == nullptr) {
return;
}
node1 -> next = node2;
connectTwoNode(node1 -> left, node1 -> right);
connectTwoNode(node2 -> left, node2 -> right);
connectTwoNode(node1 -> right, node2 -> left);
}
|