002.樹與二叉樹

在 棧和隊列 一文中提到，棧可以處理具有 完全包含 關系的問題。

而樹分為兩部分：結點 和 邊。結點可以了解為集合，邊稱為關系。樹的根結點就叫做全集，子節點叫做子集，子集并起來就得到了全集。

根結點就是待解決的問題，可能是個大問題，可以劃分為多個子問題，即是子結點。

樹也存在着一種完全包含關系。樹和棧是有一定關聯的，周遊樹的時候就要使用棧，而且使用到的是系統棧，用到系統棧的表現形式就是遞歸。

1、樹的深度、高度和度

• 樹的根結點所在層數為第一層。結點下有幾個子結點，度就為幾。
• 深度 是從根往下的層數，高度 是從最後一層往上到該結點的層數。
• 結點數量 = 邊數 + 1

2、二叉樹

計算機底層是用二進制存儲的，二進制可以表示任何進制的數。同理，二叉樹可以表示任意多的樹形結構。

通過 左孩子-右兄弟（十字連結清單法）的表示法，可以将任意的樹形結構轉化成二叉樹。

如上面的三叉樹轉化為二叉樹如下所示：

N N N 叉樹是一個非确定性問題，但是可以使用二叉樹來實作，即是将一個非确定性問題轉換為了一個确定性問題。是以如果要實作 N N N 叉樹，不需要問 N N N 是多少，隻需要實作二叉樹的結構定義即可，因為任何形式的樹形結構都能轉化成二叉樹形式。

3、二叉樹的性質

• 度為 0 的結點稱為葉子結點
• “度為 0 的結點比度為 2 的結點多 1 個”結論的推導依據：結點個數 = 邊數+ 1

推導過程： n 1 + n 0 + n 2 ( 結 點 數 ） = n 1 + 0 + 2 ∗ n 2 + 1 ( 邊 數 ) n_1 + n_0 + n_2(結點數）= n_1 + 0 + 2 * n_2 + 1 (邊數) n1​+n0​+n2​(結點數）=n1​+0+2∗n2​+1(邊數) => n 0 = n 2 + 1 n_0 = n_2 + 1 n0​=n2​+1。

其中， n 1 n_1 n1​ 表示度為 1 的結點個數， n 0 n_0 n0​ 表示度為 0 的結點個數， n 2 n_2 n2​ 表示度為 2 的結點個數。

n 0 = n 2 + 1 n_0 = n_2 + 1 n0​=n2​+1，即度為 0 的結點比度為 2 的結點多 1 個。

4、二叉樹的周遊方式

周遊即通路每個結點。

5、中國版二叉樹和國際版二叉樹

• 中國版二叉樹

  

• 國際版二叉樹

  

滿二叉樹：隻存在度為 0 和度為 2 的結點。

6、 完全二叉樹

因為子結點的編号是連續的，是以可以使用連續空間存儲。

可以根據目前結點的編号，計算出它的左右孩子的編号。即完全二叉樹可以用數組實作，每個結點可以從記錄式變為計算式。

7、廣義表

上圖的右側為該樹的幾種廣義表表示方法，通常都是使用前兩種，因為更直覺。

8、廣義表轉二叉樹的代碼實作

【要求】将廣義表還原建構為一棵二叉樹。

【思路】廣義表是用括号嵌套來表示的，而對于括号這樣的問題，可以使用棧來解決。根據左括号入棧、右括号出棧。從左到右周遊字元串，遇到非括号字元封裝成一個二叉樹結點資訊，記錄該結點的位址，遇到左括号，将目前結點入棧；下一個非括号字元也封裝成一個二叉樹結點，其父節點就是棧頂元素，需要判斷它是左孩子還是右孩子，可以根據逗号，如果沒遇到逗号，就是左孩子，取出棧頂元素，将棧頂元素的左孩子的指向該結點。遇到右括号，出棧。

【代碼】

// 廣義表轉二叉樹

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 【要求】将廣義表還原建構為一棵二叉樹。
 * 【思路】
 * 廣義表是用括号嵌套來表示的，而對于括号這樣的問題，可以使用棧來解決。根據左括号入棧、右括号出棧。
 * 從左到右周遊字元串，遇到非括号字元封裝成一個二叉樹結點資訊，記錄該結點的位址，遇到左括号，将目前結點入棧；下一個非括号字元也封裝成一個二叉樹結點，其父節點就是棧頂元素。
 * 需要判斷它是左孩子還是右孩子，可以根據逗号。如果沒遇到逗号，就是左孩子，取出棧頂元素，将棧頂元素的左孩子的指向該結點；遇到右括号，出棧。
 */

typedef struct Node { //二叉樹結點
    char data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root; //根結點
    int n; //目前節點個數
} Tree;

typedef struct Stack {
    Node **data; //開辟一片連續的存儲空間，每個位置都是存儲的Node *這樣的位址
    int top; //棧頂
    int capacity; //容量
} Stack;

/*
 * 樹結點的建立
 */
Node *createNewNode(char val) { 
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = NULL;
    p->rchild = NULL;
    return p;
}

/*
 * 樹的初始化
 */
Tree *initTree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->n = 0;
    return tree;
}

/*
 * 棧的初始化
 */
Stack *initStack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (Node **)malloc(sizeof(Node *) * n);
    s->top = -1;
    s->capacity = n;
    return s;
}

/*
 * 擷取棧頂元素
 */
Node *top(Stack *s) {
    return s->data[s->top];
}


/*
 * 判斷棧是否為空
 */
int isEmpty(Stack *s) {
    return s->top == -1;
}

/*
 * 入棧
 */
int push(Stack *s, Node *val) {
    if (s == NULL) return -1;
    if (s->top == s->capacity - 1) return -1;
    s->data[++(s->top)] = val;
    return 0;
}


/*
 * 出棧
 */
int pop(Stack *s) {
    if (s == NULL) return -1;
    if (isEmpty(s)) return -1;
    s->top--;
    return 0;
}

/*
 * 棧的銷毀
 */
void destroyStack(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}

/*
 * 二叉樹結點的銷毀
 */
void destroyNode(Node *node) {
    if (node == NULL) return ;
    destroyNode(node->lchild);
    destroyNode(node->rchild);
    free(node);
    return ;
 }

/*
 * 二叉樹的銷毀
 */
void destroyTree(Tree *tree) {
    if (tree == NULL) return ;
    destroyNode(tree->root);
    free(tree);
    return ;
}

/*
 * 廣義表轉二叉樹
 */
 Node *buildNode(const char *str, int *node_cnt) {
    Stack *s = initStack(strlen(str));
    Node *temp = NULL;
    Node *p = NULL; //p記錄根結點，即棧中最後彈出的元素
    int flag = 0;
    while (str[0]) {
        switch (str[0]) {
            case '(':
                push(s, temp);
                flag = 0;
                break;
            case ')':
                p = top(s);
                pop(s);
                break;
            case ',':
                flag = 1;
                break;
            case ' ': 
                break;
            default:
                temp = createNewNode(str[0]);
                if (!isEmpty(s) && flag == 0) {
                    top(s)->lchild = temp;
                } else if (!isEmpty(s) && flag == 1) {
                    top(s)->rchild = temp;
                }
                ++(*node_cnt);
                break;
        }
        ++str;
    }
    if (p == NULL) p = temp; //隻有一個結點時因為沒有括号，就沒有了入棧操作，故單獨判斷這種情況 
    destroyStack(s);
    return p;
}

/*
 * 先序周遊
 */
void pre_order_node(Node *node) {
    if (node == NULL) return ;
    printf("%c ", node->data);
    pre_order_node(node->lchild);
    pre_order_node(node->rchild);
    return ;
}

/*
 * 先序周遊：傳入根結點
 */
void pre_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("pre_order: ");
    pre_order_node(tree->root);
    printf("\n");
    return ;
}


/*
 * 中序周遊
 */
void in_order_node(Node *node) {
    if (node == NULL) return ;
    in_order_node(node->lchild);
    printf("%c ", node->data);
    in_order_node(node->rchild);
    return ;
}


void in_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("in_order: ");
    in_order_node(tree->root);
    printf("\n");
}

/*
 * 後序周遊
 */
void post_order_node(Node *node) {
    if (node == NULL) return ;
    post_order_node(node->lchild);
    post_order_node(node->rchild);
    printf("%c ", node->data);
    return ;
}

void post_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("post_order: ");
    post_order_node(tree->root);
    printf("\n");
    return ;
}


int main() {
    char str[1000] = {0};
    int node_cnt = 0;
    scanf("%[^\n]s", str);
    Tree *tree = initTree(); //二叉樹初始化
    tree->root = buildNode(str, &node_cnt); //廣義表轉二叉樹結點
    tree->n = node_cnt;
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    destroyTree(tree);
    return 0;
}
           

測試結果：

A(B(,D),C(E,)) # 輸入
pre_order: A B D C E
in_order: B D A E C
post_order: D B E C A
           

9、二叉搜尋樹的代碼實作

二叉搜尋樹的特點：左子樹結點的值 < 根結點的值 < 右子樹結點的值。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 * 二叉搜尋樹結點定義
 */
typedef struct Node {
    int val;
    struct Node *lchild;
    struct Node *rchild;
} Node;

/*
 * 樹的結構定義
 */
typedef struct Tree {
    Node *root;
    int cnt;
} Tree;

/*
 * 結點初始化
 */
Node *init_node(int val) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

/*
 * 樹的初始化
 */
Tree *init_tree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->cnt = 0;
    return tree;
}

/*
 * 銷毀結點
 */
void destroy_node(Node *node) {
    if (node == NULL) return ;
    destroy_node(node->lchild);
    destroy_node(node->rchild);
    free(node);
    return ;
}

/*
 * 銷毀樹
 */
void destroy_tree(Tree *tree) {
    if (tree == NULL) return ;
    destroy_node(tree->root);
    free(tree);
    return ;
}

/*
 * 結點的插入
 */
Node *insert_node(Node *root, int val, int *flag) {
    if (root == NULL) {
        *flag = 1;
        return init_node(val);
    }
    if (root->val == val) return root; //待插入的值與根節點值相等，不做任何插入操作
    if (val < root->val)  //待插入的值比根節點值小，則要插在左子樹上
        root->lchild = insert_node(root->lchild, val, flag);
    else //待插入的值比根節點值大，則要插在右子樹上
        root->rchild = insert_node(root->rchild, val, flag);
    return root;
}

/*
 * 插入操作
 */
void insert(Tree *tree, int val) {
    int flag = 0;
    tree->root = insert_node(tree->root, val, &flag);
    tree->cnt += flag; //如果flag = 1，表示插入成功，更新節點數
    return ;
}

/*
 * 先序周遊
 */
void pre_order_node(Node *node) {
    if (node == NULL) return ;
    printf("%d ", node->val);
    pre_order_node(node->lchild);
    pre_order_node(node->rchild);
    return ;
}


void pre_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("pre_order: ");
    pre_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 中序周遊
 */
void in_order_node(Node *node) {
    if (node == NULL) return ;
    in_order_node(node->lchild);
    printf("%d ", node->val);
    in_order_node(node->rchild);
    return ;
}


void in_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("in_order: ");
    in_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 後序周遊
 */
void post_order_node(Node *node) {
    if (node == NULL) return ;
    post_order_node(node->lchild);
    post_order_node(node->rchild);
    printf("%d ", node->val);
    return ;
}


void post_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("post_order: ");
    post_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 節點值的列印
 */
void output_node(Node *node) {
    if (node == NULL) return ;
    printf("%d", node->val);
    if (node->lchild == NULL && node->rchild == NULL) return ;
    printf("(");
    output_node(node->lchild);
    printf(",");
    output_node(node->rchild);
    printf(")");
    return ;
}

/*
 * 二叉樹轉廣義表
 */
void output(Tree *tree) {
    if (tree == NULL) return ;
    printf("tree(%d) : ", tree->cnt);
    output_node(tree->root);
    printf("\n");
    return ;
}


int main() {
    srand(time(0));
    Tree *tree = init_tree();
    #define max_op 10
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        insert(tree, val);
        output(tree);
    }
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    #undef max_op
    destroy_tree(tree);

    return 0;
}
           

測試結果：

tree(2) : 7(,62)
tree(3) : 7(,62(48,))
tree(4) : 7(,62(48(19,),))
tree(5) : 7(,62(48(19,),68))
tree(6) : 7(,62(48(19,),68(,90)))
tree(7) : 7(6,62(48(19,),68(,90)))
tree(8) : 7(6,62(48(19(17,),),68(,90)))
tree(9) : 7(6,62(48(19(17,),),68(,90(71,))))
tree(10) : 7(6,62(48(19(17,),53),68(,90(71,))))
pre_order: 7 6 62 48 19 17 53 68 90 71
in_order: 6 7 17 19 48 53 62 68 71 90
post_order: 6 17 19 53 48 71 90 68 62 7
           

10、相關題目

Leetcode 100.相同的樹

【思路】判斷兩棵樹是否相同，就是判斷兩棵樹的各個結點的資料域是否相同，于是需要周遊比較兩棵樹的相同位置的結點，當然需要使用到遞歸，遞歸結束的邊界條件就是目前比較的兩個結點存在的各種情況。

【代碼】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if (p == NULL && q == NULL) return true;
    if (p == NULL || q == NULL) return false;
    if (p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
           

Leetcode 101.對稱二叉樹

【思路】和Leetcode 100 是相同的思路，不過是對稱地進行比較。

【代碼】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSame(struct TreeNode *left_node, struct TreeNode *right_node) {
    if (left_node == NULL && right_node == NULL) return true;
    if (left_node == NULL || right_node == NULL || left_node->val != right_node->val) return false;
    return isSame(left_node->left, right_node->right) && isSame(left_node->right, right_node->left);
}

bool isSymmetric(struct TreeNode* root){
    return isSame(root->left, root->right);
}
           

Leetcode 102.二叉樹的層序周遊

【思路】BFS，但是和一般的BFS的差別在于，每次并不隻是隻出隊一個元素，而是出隊同一層的所有元素。

【代碼】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//1.判斷一層結束:同一層元素處理完畢之後進行下一次疊代，疊代次數就是層數
//2.每層的節點個數：目前隊列中的元素個數
//returnSize記錄結果中二維數組的行數，returnColumnSizes記錄每行的個數
#define max 1024
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    //隊列存放樹節點
    struct TreeNode *queue[max]; //靜态數組
    int head = 0, tail = 0;

    int **ans = malloc(sizeof(int *) * max);
    *returnColumnSizes = malloc(sizeof(int) * max);

    int level = 0, count = 0; //level為層數
    queue[tail++] = root; //根節點入隊
    count++;

    while (head != tail) {
        count = tail - head; //目前隊列中的元素個數
        (*returnColumnSizes)[level] = count; //記錄目前層的元素個數
        //存儲目前層的元素
        ans[level] = malloc(sizeof(int) * count);
        //相比于普通的隊列出隊，這裡是将同一層的元素全部出隊
        for (int i = 1; i <= count; i++) { //出隊同一層的元素
            struct TreeNode *p = queue[head++];
            ans[level][i - 1] = p->val;
            if (p->left) queue[tail++] = p->left; //入隊剛剛出隊元素的左孩子子結點
            if (p->right) queue[tail++] = p->right;
        }
        level++;
    }
    *returnSize = level; //記錄總的層數
    return ans;
}
           

Leetcode 104. 二叉樹的最大深度

【思路】遞歸周遊二叉樹節點，同時記錄深度。

【代碼】

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    void func(TreeNode *p, int depth) {
        if (p == nullptr) return ;
        ans = max(ans, depth);
        func(p->left, depth + 1);
        func(p->right, depth + 1);
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        func(root, 1);
        return ans;
    }
};
           

Leetcode 107. 二叉樹的層序周遊 II

【思路】思路同Leetcode102題，隻是最後将結果進行反轉。

【代碼】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 #define max 1024
int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * max);
    int head = 0, tail = 0, count = 0, level = 0;

    *returnColumnSizes = malloc(sizeof(int) * max);//一維數組
    int **ans = (int **)malloc(sizeof(int *) * max);

    queue[tail++] = root;
    count++;

    while (head != tail) {
        count = tail - head; //每層節點個數
        (*returnColumnSizes)[level] = count; //記錄level層的節點個數
        ans[level] = malloc(sizeof(int) * count);//開辟空間存儲每一層的每個節點
    
        for (int i = 1; i <= count; i++) {
            struct TreeNode *p = queue[head++];
            ans[level][i - 1] = p->val;
            if (p->left) queue[tail++] = p->left;
            if (p->right) queue[tail++] = p->right;
        }
        level++;
    }
    *returnSize = level;

    for (int i = 0, j = level- 1; i < j; i++, j--) {
        //交換層
        int *temp1 = ans[i];
        ans[i] = ans[j];
        ans[j] = temp1;
        //交換每一層的節點個數
        int *temp2 = (*returnColumnSizes)[i];
        (*returnColumnSizes)[i] = (*returnColumnSizes)[j];
        (*returnColumnSizes)[j] = temp2;
    }

    return ans;

}
           

Leetcode 110.平衡二叉樹

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int height(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    } 
    return fmax(height(root->left), height(root->right)) + 1;
}


bool isBalanced(struct TreeNode* root){
    if (root == NULL) return true;
    return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
           

Leetcode 111.二叉樹的最小深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//深搜 DFS
int minDepth(struct TreeNode* root){
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;

    int ans = INT_MAX;

    if (root->left != NULL) ans = fmin(ans, minDepth(root->left));
    if (root->right != NULL) ans = fmin(ans, minDepth(root->right));

    return ans + 1;
}
           

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//廣搜：此處使用了數組實作隊列，可以使用連結清單實作更節省空間
struct QueueNode {
    int head, tail;
    struct TreeNode **data;
    int capacity;
};

struct QueueNode *init(int n) {
    struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    node->head = 0;
    node->tail = 0;
    node->data = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * n);
    node->capacity = n;
    return node;
}

int minDepth(struct TreeNode* root){
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    
    struct QueueNode *que = init(100000);
    que->data[(que->tail)++] = root;
    int depth = 1;
    while (que->head != que->tail) {
        int size = (que->tail - que->head); //計算隊列中的元素
        for (int i = 0; i < size; i++) { //處理每層的節點
            struct TreeNode *temp = que->data[que->head++];
            if (temp->left != NULL) {
                que->data[(que->tail)++] = temp->left;
            }
            if (temp->right != NULL) {
                que->data[(que->tail)++] = temp->right;
            }

            if (temp->left == NULL && temp->right == NULL) {
                return depth;
            }
        }
        depth++;
    }
    return false;
}
           

Leetcode 112. 路徑總和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool hasPathSum(struct TreeNode* root, int targetSum){
    if (root == NULL) return false;
    if (root->left == NULL && root->right == NULL && root->val == targetSum) return true;

    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
           

Leetcode 226. 翻轉二叉樹

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root){
    if (root == NULL) return NULL;
    struct TreeNode *left = root->left;
    root->left = root->right;
    root->right = left;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
           

Leetcode 235. 二叉搜尋樹的最近公共祖先

【思路】一次周遊。利用二叉搜尋樹的性質，分為三種情況：

1. 如果目前節點大于

   p

   和

   q

   的值，則

   p

   和

   q

   的最近公共祖先在目前節點的左子樹；
2. 如果目前節點小于

   p

   和

   q

   的值，則

   p

   和

   q

   的最近公共祖先在目前節點的右子樹；
3. 如果上述情況都不滿足，則目前節點就是"分岔節點"，此時要麼

   p

   和

   q

   在目前節點的不同子樹中，要麼其中一個節點就是目前節點。

【代碼】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode *ancestor = root;
    while (true) {
        if (ancestor->val > p->val && ancestor->val > q->val) {
            ancestor = ancestor->left;
        } else if (ancestor->val < p->val && ancestor->val < q->val) {
            ancestor = ancestor->right;
        } else {
            break;
        }
    }
    
    return ancestor;
}
           

Leetcode 257.二叉樹的所有路徑

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    //深搜
    void construct_paths(TreeNode *root, string path, vector<string> &paths) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left == nullptr && root->right == nullptr) { //目前節點是葉子節點
                paths.push_back(path); //路徑加入到答案中
            } else {
                path += "->"; //目前節點不是葉子節點，繼續遞歸周遊
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        construct_paths(root, "", ans);
        return ans;
    }
};
           

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    //廣搜
    typedef struct {
        TreeNode *node;
        string val;
    } Node;
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        queue<Node> que;

        que.push({root, to_string(root->val)});

        while (!que.empty()) {
            TreeNode *node = que.front().node;
            string path = que.front().val;
            que.pop();

            if (node->left == nullptr && node->right == nullptr) {
                ans.push_back(path);
            } else {
                if (node->left != nullptr) {
                    que.push({node->left, path + "->" + to_string(node->left->val)});
                } 
                if (node->right != nullptr) {
                    que.push({node->right, path + "->" + to_string(node->right->val)});
                }
            }
        }
        return ans;
    }
};
           

Leetcode 297.二叉樹的序列化與反序列化

【思路】深搜，先序周遊得到先序序列，反序列化就根據先序序列得到一棵樹。

【代碼】官方題解

/**
 * 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:
    //深搜，先序周遊得到序列
    void rserialize(TreeNode *root, string &str) {
        if (root == nullptr) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ret;
        rserialize(root, ret);
        return ret;
    }

    //根據"None"解析先序周遊的序列得到一棵樹
    TreeNode *rdeserialize(list<string> &dataArray) {
        if (dataArray.front() == "None") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }
        TreeNode *root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    } 

    // 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 rdeserialize(dataArray);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
           

【複雜度分析】

• 時間複雜度： O ( n ) O(n) O(n)。序列化和反序列化函數中，每個節點隻通路一次，是以時間複雜度是 O ( n ) O(n) O(n)，其中 n n n 為節點數，即樹的大小。
• 空間複雜度： O ( n ) O(n) O(n)。序列化和反序列化函數中，遞歸會用到棧空間，遞歸的深度即為空間複雜度，故漸進空間複雜度為 O ( n ) O(n) O(n)。