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) {}
};递归方法完成二叉树的遍历，每个节点都能回到三次。
void f(TreeNode* head){
// 1
if(head == nullptr){
return;
}
// 1：第一次回到自己
f(head->left);
// 2
// 2：第二次回到自己
f(head->right);
// 3
// 3：第三次回到自己
}- 先序
void preOrderRecur(TreeNode* head){
if(head == nullptr){
return;
}
cout << head->value << " ";
preOrderRecur(head->left);
preOrderRecur(head->right);
}- 中序
void inOrderRecur(TreeNode* head){
if(head == nullptr){
return;
}
inOrderRecur(head->left);
cout << head->value << " ";
inOrderRecur(head->right);
}- 后序
void posOrderRecur(TreeNode* head){
if(head == nullptr){
return;
}
posOrderRecur(head->left);
posOrderRecur(head->right);
cout << head->value << " ";
}-
先序（深度优先遍历）
- 先把头节点 head 放到栈中
- (1) 从栈中弹出一个节点 cur
- (2) 打印/处理 cur
- (3) 先压右再压左 (没有就什么也不做)
- (4) 循环
✅tested
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root){
return res;
}
stack<TreeNode*> s;
s.push(root);
while(!s.empty()){
TreeNode* cur = s.top();
s.pop();
res.push_back(cur->val);
if(cur->right){
s.push(cur->right);
}
if(cur->left){
s.push(cur->left);
}
}
return res;
}-
后序 (将先序遍历加工)
- 先序' (头右左)
- 先把头节点 head 放到栈中
- (1) 从栈中弹出一个节点 cur
- (2) cur 放到收集栈中
- (3) 先压左再压右 (没有就什么也不做)
- (4) 循环
✅tested
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root){
return res;
}
stack<TreeNode*> s;
s.push(root);
stack<TreeNode*> sRes;
while(!s.empty()){
TreeNode* cur = s.top();
s.pop();
sRes.push(cur);
if(cur->left){
s.push(cur->left);
}
if(cur->right){
s.push(cur->right);
}
}
while(!sRes.empty()){
res.push_back(sRes.top()->val);
sRes.pop();
}
return res;
}-
中序
- 整棵树左边界进栈
- 依次弹出过程中打印
- 对弹出节点的右树重复
✅tested
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
while(!s.empty() || root){
while(root){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}宽度优先遍历用 队列，弹出就打印，先放左再放右
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if(!root){
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
res.push_back(cur->val);
q.pop();
if(cur->left){
q.push(cur->left);
}
if(cur->right){
q.push(cur->right);
}
}
return res;
}✅tested
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root){
return res;
}
queue<TreeNode*> q;
q.push(root);
TreeNode* curEnd = root; //当前层的最后一个节点
TreeNode* nextEnd = nullptr;//下一层的最后一个节点
vector<int> tmp;
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
tmp.push_back(cur->val);
if(cur->left){
q.push(cur->left);
nextEnd = cur->left;
}
if(cur->right){
q.push(cur->right);
nextEnd = cur->right;
}
if(cur == curEnd){
res.push_back(tmp);
tmp.clear();
curEnd = nextEnd;
nextEnd = nullptr;
}
}
return res;
}- 使用哈希表的方法
int getMaxWidth(TreeNode* head){
if(head == nullptr){
return 0;
}
int maxWidth = 0; // 哪一层的节点数目是最多的
int curWidth = 0;
int curLevel = 0; // 当前在哪一层
unordered_map<TreeNode*, int> levelMap; //节点在第几层
levelMap.insert(pair<TreeNode*, int>(head, 1));
queue<TreeNode*> q;
q.push(head);
TreeNode* node = nullptr;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
while (!q.empty()){
node = q.front();
left = node->left;
right = node->right;
q.pop();
int curLevelNodes = levelMap.at(node); // 节点所在的层数
if(curLevelNodes == curLevel){
curWidth++;
}
else{
maxWidth = max(maxWidth, curWidth);
curLevel++;
curLevelNodes = 1;
}
if(left != nullptr){
levelMap.insert(pair<TreeNode*, int>(left, levelMap.at(node) + 1));
q.push(left);
}
if(right != nullptr){
levelMap.insert(pair<TreeNode*, int>(right, levelMap.at(node) + 1));
q.push(right);
}
}
return maxWidth;
}- 不使用哈希表的方法
int getMaxWidth2(TreeNode* root) {
if(!root){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int maxWidth = -1;
int curLevelNodes = 0; // 当前层的节点数
TreeNode* curEnd = root; // 当前层的最后一个节点
TreeNode* nextEnd = nullptr;// 下一层的最后一个节点
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
curLevelNodes++;
if(cur->left){
q.push(cur->left);
nextEnd = cur->left;
}
if(cur->right){
q.push(cur->right);
nextEnd = cur->right;
}
if(cur == curEnd){
maxWidth = max(maxWidth, curLevelNodes);
curEnd = nextEnd;
nextEnd = nullptr;
}
}
return maxWidth;
}搜索二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为搜索二叉树；
[提示] 中序遍历 是升序
✅tested
long long preValue = (long long)INT_MIN - 1;
bool isValidBST(TreeNode* root) {
if(!root){
return true;
}
bool isLeftBST = isValidBST(root->left);
if(!isLeftBST){
return false;
}
if(root->val <= preValue){
return false;
}
preValue = root->val;
return isValidBST(root->right);
}- 非递归写法
✅tested
bool isValidBST2(TreeNode* root) {
if(!root){
return true;
}
long long preValue = (long long)INT_MIN - 1;
stack<TreeNode*> s;
TreeNode* cur = root;
while(!s.empty() || cur){
while(cur){
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
if(cur->val <= preValue){
return false;
}
preValue = cur->val;
cur = cur->right;
}
return true;
}- 递归套路解法
[提示] 宽度优先遍历
(1) 任何一个节点，有右无左，返回false
(2) 在(1)不违规的条件下，如果遇到第一个左右子树不全的节点，后续节点必须都是叶节点
✅tested
bool isCompleteTree(TreeNode* root) {
if(!root){
return true;
}
bool isLeaf = false; // 是否遇到过左右子树不全的节点
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
if((cur->right && !cur->left) || (isLeaf && (cur->left || cur->right))){
return false;
}
if(cur->left){
q.push(cur->left);
}
if(cur->right){
q.push(cur->right);
}
if(!cur->left || !cur->right){
isLeaf = true;
}
}
return true;
}[提示] 先求二叉树的最大深度L，再求二叉树的节点个数N
N = 2^L - 1
- 二叉树的递归套路
struct Info{
Info(int h, int n) : height(h),nodes(n){ }
int height;
int nodes;
};
Info f(TreeNode* head){
if(!head){
return Info(0, 0);
}
Info leftData = f(head->left);
Info rightData = f(head->right);
int height = max(leftData.height, rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes + 1;
return Info(height, nodes);
}
bool isFBT(TreeNode* head){
if(head == nullptr){
return true;
}
Info data = f(head);
return data.nodes == ((data.height << 1) - 1);
}树型DP（动态规划）
二叉树的递归套路：
-
向左树要信息
-
向右树要信息
-
加工自己的信息
✅tested
struct ReturnType{
bool m_isBal;
int m_height;
ReturnType(bool isBal, int height) : m_isBal(isBal), m_height(height) { }
};
ReturnType process(TreeNode* root){
if(!root){
return ReturnType(true, 0);
}
ReturnType leftInfo = process(root->left);
ReturnType rightInfo = process(root->right);
bool isBal = leftInfo.m_isBal && rightInfo.m_isBal && abs(leftInfo.m_height - rightInfo.m_height) < 2;
int height = max(leftInfo.m_height, rightInfo.m_height) + 1;
return ReturnType(isBal, height);
}
bool isBalanced(TreeNode* root) {
if(!root){
return true;
}
return process(root).m_isBal;
}node1 和 node2 一定属于head为头的树
方法一：
- 记录每个节点的头节点
- 记录node1往上一直到头节点的节点有哪些
- 比较node2往上的过程中是否遇到node1中记录的节点
✅tested
void process(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& fatherMap){
if(!root){
return;
}
fatherMap.insert(pair<TreeNode*, TreeNode*>(root->left, root));
fatherMap.insert(pair<TreeNode*, TreeNode*>(root->right, root));
process(root->left, fatherMap);
process(root->right, fatherMap);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root){
return NULL;
}
unordered_map<TreeNode*, TreeNode*> fatherMap;
fatherMap.insert(pair<TreeNode*, TreeNode*>(root, root));
process(root, fatherMap);
unordered_set<TreeNode*> s;
TreeNode* cur = p;
while(cur != fatherMap[cur]){
s.insert(cur);
cur = fatherMap[cur];
}
s.insert(root);
cur = q;
while(cur != fatherMap[cur]){
if(s.find(cur) != s.end()){
return cur;
}
cur = fatherMap[cur];
}
return root;
} 方法二：
(1) o1是o2的LCA，或o2是o1的LCA
(2) o1与o2不互为LCA
✅tested
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q){
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right){
return root;
}
return left != NULL? left : right;
}中序遍历中，一个节点的下一个节点
[题目] 现在有一种新的二叉树节点类型如下
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { }
};该结构比普通二叉树节点结构多了一个指向父节点的next指针。
假设有一棵Node类型的节点组成的二叉树，树中每个节点的next指针都正确地指向自己的父节点，头节点的next指向null。
只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。
在二叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点。
[提示]
(1) x 有右树时，右树上的最左节点
(2) x 无右树，往上走，判断当前节点是否是父节点的左孩子
(3) 整棵树最右侧的节点无后继节点
✅tested
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
if(pNode == nullptr){
return nullptr;
}
TreeLinkNode* cur = pNode->right;
if(cur != nullptr){
while(cur->left){
cur = cur->left;
}
}else{
cur = pNode->next;
while(cur->left != pNode && cur != nullptr){
pNode = cur;
cur = cur->next;
}
}
return cur;
}就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树
如何判断一颗二叉树是不是另一棵二叉树的子树？
✅tested
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root){
return "#_";
}
string data = to_string(root->val) + "_";
data += serialize(root->left);
data += serialize(root->right);
return data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
list<string> dataArray;
string str;
for(auto& ch : data){
if(ch == '_'){
dataArray.push_back(str);
str.clear();
}
else{
str.push_back(ch);
}
}
if(!str.empty()){
dataArray.push_back(str);
str.clear();
}
return deserializeSub(dataArray);
}
TreeNode* deserializeSub(list<string>& dataArray){
if(dataArray.front() == "#"){
dataArray.erase(dataArray.begin());
return NULL;
}
TreeNode* head = new TreeNode(stoi(dataArray.front()));
dataArray.erase(dataArray.begin());
head->left = deserializeSub(dataArray);
head->right = deserializeSub(dataArray);
return head;
}请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。
请从上到下打印所有折痕的方向。
例如：N=1时，打印：down。N=2时，打印：down down up
void printProcess(int i, int N, bool down){
if(i > N){
return;
}
printProcess(i+1, N, true);
cout << (down ? "凹" : "凸") << " ";
printProcess(i+1 , N, false);
}
void printAllfolds(int N){
printProcess(1, N, true);
}