二叉树

SyEic_L MVP++
  2025-10-02 17:59:28 2025-10-02 17:59:28 Created   2025-10-02 17:59:28 2025-10-02 17:59:28 Updated    1.7k Words  8 Mins  

遍历

递归

1
2
3
4
5
6
7
void recur(Node* head){
    if (head == NULL){
        return ;
    }
    recur(head->left);
    recur(head->right);
}

非递归

先序遍历(深度优先)

  1. 从栈中弹出一个节点cur
  2. 打印（处理）cur
  3. 先右后左加入栈（如果存在）
  4. 循环1、2、3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void preOrderUnrecur(Node* head) {
    if (head != NULL) {
        stack<Node*> st;
        st.push(head);
        while (!st.empty()) {
            head = st.top();
            st.pop();
            cout << head->value << endl;
            if (head->right != NULL) {
                st.push(head->right);
            }
            if (head->left != NULL) {
                st.push(head->left);
            }
        }
    }
}

中序遍历

  1. 每棵子树整个左边界进栈
  2. 依次弹出并打印（处理）
  3. 如果有右树重复1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void inOrderUnRecur(Node* head){
    if (head != NULL){
        stack<Node*> st;
        while(!st.empty() || head != NULL){
            if (head != NULL){
                st.push(head);
                head = head->left;
            }
            else{
                head = st.top();
                st.pop();
                cout << head-> value >> endl;
                head = head-> right;
            }
        }
    }
}

后序遍历

  1. 创建一个收集栈
  2. 从原始栈中弹出cur
  3. cur进收集栈
  4. 先左后右进原始栈
  5. 循环2、3、4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void posOrderUnrecur(Node* head){
    if (head != NULL){
        stack<Node*> s1;
        stack<Node*> s2;
        s1.push(head);
        while(!s1.empty()){
            head = s1.top();
            s1.pop();
            s2.push(head);
            if (head->left != NULL){
                s1.push(head->left);
            }
            if (head->right != NULL){
                s1.push(head->right);
            }
        }
        while(!s2.empty()){
            cout << s2.top() << endl;
            s2.pop();
        }
    }
}

广度优先遍历

  1. 队列弹出cur
  2. 先左后右加入队列
  3. 循环1、2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BFS(Node* head){
    if (head != NULL){
        queue<Node*> q;
        q.enqueue(head);
        while(!q.empty()){
            Node* head = q.dequeue();
            cout << head->value << endl;
            if (head->left != NULL){
                q.enqueue(head->left);
            }
            if (head->right != NULL){
                q.enqueue(head->right);
            }
        }
    }
}

搜索二叉树

每一棵左子树的值都比当前节点小，右子树的值都比当前节点大

判断

通过中序遍历比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isBST(Node* head){
    if (head != NULL){
        int preValue = INT_MIN;
        stack<Node*> st;
        while(!st.empty() || head != NULL){
            if (head != NULL){
                st.push(head);
                head = head->left;
            }
            else{
                head = st.top();
                st.pop();
                if (head->value <= preValue){
                    return false;
                }
                else{
                    preValue = head->value;
                }
                head = head-> right;
            }
        }
    }
}

完全二叉树

除最后一层都是满的，最后一层就算不满也是从左到右依次变满

判断

  • 广度优先遍历
  • 任意节点如果有右子无左子 false
  • 遇到第一个左右子节点不全，则剩余节点必须都是叶节点
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
bool isCBT(Node* head){
    if (head == NULL){
        return true;
    }
    Queue<Node*> q;
    bool leaf = false;	//判断是否遇到过子节点不全的情况
    Node* l = NULL;
    Node* r = NULL;
    q.enqueue(head);
    while (!q.empty()){
        head = q.dequeue();
        l = head->left;
        r = head->right;
        if ((leaf && (l != NULL || r != NULL)) || (l == NULL && r != NULL)){
            return false;
        }
        if (l != NULL){
            q.enqueue(l);
        }
        if (r != NULL){
            q.enqueue(r);
        }
        if (l == NULL || r == NULL){
            leaf = true;
        }
    }
    return true;
}

满二叉树

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
bool isFBT(Node* head){
    if (head == NULL){
        return true;
    }
    Info data = process(head);
    return data.node == (1 << data.heigth - 1);
}

class Info{
    int height;
    int nodes;
    public:
    Info(int h, int n){
        height = h;
        nodes = n;
    }
}

Info process(Node* x){
    if (x = NULL){
        return new Info(0, 0)
    }
    Info leftData = process(x.left);
    Info rightData = process(x.right);
    int height = max(leftData.height, rightData.height) + 1;
    int nodes = leftData.nodes + rightDatta.nodes + 1;
    return new Info(height, nodes);
}

平衡二叉树

对于任何一个子树，其左数和右树的高度差不超过1

判断

  • 左子树是平衡
  • 右子树是平衡
  • 左右子树高度差不超过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
bool isBalanced(Node* head){
    return process(head).isBalanced;
}

class ReturnType{
    bool isBalanced;
    int height;
	public:
    ReturnType(bool isB, int hei){
        isBalanced = isB;
        height = hei;
    }
};

ReturnType process(Node* x){
    if (x == NULL){
        return new ReturnType(true, 0);
    }
    ReturnType leftData = process(x->left);
    ReturnType rightData = process(x->right);
    int height = max(leftData.height, rightData.height) + 1;
    bool isBalanced = leftData.isBalanced && rightData.balanced && abs(leftData.height - rightData.height) <= 1;
    return new RetunType(isBalanced, height);
}

树形DP

  • 向左子树要需要的内容
  • 向右子树要需要的内容
  • 得出当前节点的相关内容

题目

最低公共祖先节点

给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

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
Node* lca(Node* head, Node* o1, Node* o2){
    unordered_map<Node*, Node*> fatherMap;
    fatherMap.enplace(head, head);
    process(head, fatherMap);
    unordered_set<Node*> set1;
    
    Node* cur = o1;
    while (cur != fatherMap.at(cur)){
        set1.insert(cur);
        cur = fatherMap.at(cur);
    }
    set1.insert(head);
    
    Node* cur = o2;
    while (cur != fatherMap.at(cur)){
        if (set1.find(cur) != set1.end()){
            return cur;
        }
        else{
            cur = fatherMap.at(cur);
        }
    }
    return nullptr;
}

void process(Node* head, unordered_map<Node*, Node*> fatherMap){
    if (head == NULL){
        return ;
    }
    fatherMap.enplace(head->left, head);
    fatherMap.enplace(head->right, head);
    process(head->left, fatherMap);
    process(head->right, fatherMap);
}
1
2
3
4
5
6
7
8
9
10
11
Node* lowestAncestor(Node* head, Node* o1, Node* o2){
    if (head == NULL || head == o1 || head == o2){
        return head;
    }
    Node* left = lowestAncestor(head->left, o1, o2);
    Node* right = lowestAncestor(head->right, o1, o2);
    if (left != NULL && right != NULL){
        return head;
    }
    return left != NULL ? left : right;
}

后继节点

求中序遍历中该节点的下一个节点

  1. 常规二叉树通过中序遍历列表查找
  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
Node* getSuccessorNode(Node* node){
    if (node == NULL){
        return node;
    }
    if (node->right != NULL){
        return getLeftMost(node->right);	//返回最左子节点
    }
    else{	//无右子树
        Node* parent = node->parent;
        while (parent != NULL && parent->left != node){
            nmode = parent;
            parent = node->parent;
        }
        return parent;
    }
}

Node* getLeftMost(Node* node){
    if (node == NULL){
        return node;
    }
    while (node->left != NULL){
        node = node->left;
    }
    return node;
}

序列化和反序列化

  • 序列化：将内存中一棵树变成字符串形式
  • 反序列化：将字符串形式还原为内存中的树

中序序列化

1
2
3
4
5
6
7
8
9
10
// #表示空 _表示分隔符
string serialByPre(Node* head){
    if (head == NULL){
        return "#_";
    }
    string res = head->value + "_";
    res += serialByPre(head->left);
    res += serialByPre(head->right);
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* reconByPreString(string preStr){
    stringstream ss(preStr);
    string token;
    queue<string> q;
    while (getline(ss, token, '_')){
        q.enqueue(token);
    }
    return reconPreOrder(q);
}

Node* reconPreOrder(queue<string> q){
    string value = queue.dequeue();
    if (value.equlas("#")){
        return NULL;
    }
    Node* head = new Node(stoi(value));
    head->left = reconPreOrder(q);
    head->right = reconPreOrder(q);
    return head;
}

google折纸问题

将一段纸条放在桌上，然后从纸条下边向上方对折1次，压出折痕后展开，此时折痕是凹下去的（称为凹折痕），即折痕凸起的方向指向纸条的背面。如果从纸条的下边向上方连续对折两次，压出折痕后展开，此时有三条折痕，从上到下依次是（凹折痕 -> 凹折痕 -> 凸折痕）。
给定一个参数N，代表纸条从下向上连续对折N次。从上到下打印所有折痕的方向。

google折纸

1
2
3
4
5
6
7
8
9
10
11
12
13
void printAllFolds(int N){
    printProcess(1, N, true);
}

//i是节点的层数，N是一共的层数， down == true 凹; down == false 凸
void printProcess(int i, int N, bool down){
    if (i > n){
        return;
    }
    printProcess(i+1, N, true);
    cout << (down? "凹" : "凸") << endl;
    printProcess(i+1, N, false);
}
  • Title: 二叉树
  • Author: SyEic_L
  • Created at : 2025-10-02 17:59:28
  • Updated at : 2025-10-02 17:59:28
  • Link: https://blog.syeicl.vip/2025/10/02/二叉树/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
树 树 数组、串与广义表 数组、串与广义表 排序 排序
推荐阅读
树 树 数组、串与广义表 数组、串与广义表
Comments
On this page
二叉树
  1. 遍历
    1. 递归
    2. 非递归
  2. 搜索二叉树
  3. 完全二叉树
  4. 满二叉树
  5. 平衡二叉树
  6. 树形DP
  7. 题目
    1. 最低公共祖先节点
    2. 后继节点
    3. 序列化和反序列化
    4. google折纸问题