结构|二叉树

作者: doraTrager | 来源:发表于2019-12-21 15:38 被阅读0次

初识数据结构之二叉搜索树
数据结构 - 概要
二叉树的总结
数据结构课程第七周树和二叉树
【恋上数据结构与算法一】(六)二叉树
二叉树
数据结构之二叉树(一)——绪论
二叉树
二叉树
61_二叉树的存储结构设计

学习笔记，可能有些谬误，请批判性阅读。

二叉树是树结构的入门款。
以下是二叉树的类定义。

class TreeNode{
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val){
        val = val;
    }
    ~TreeNode();
    
};

任意二叉树的LCA

LCA是最低公共祖先（lowest common ancestor）。
先看普通二叉树的吧，好理解一点。
思路就是，先分别在左右子树中查找LCA，若返回均不为空，则LCA为当前root；否则左右子树返回的非空的LCA（若都为空，则返回空）。

TreeNode* get_lca(TreeNode* root, TreeNode* p, TreeNode* q){
    if(root == NULL){
        return root;
    }
    left = get_lca(root->left, p, q);
    right = get_lca(root->right, p, q);
    if(left && right){
        return root;
    }
    return left != NULL? left: right;
}

二叉查找树的LCA

二叉查找树（Binary Search Tree, BST）的性质是，每个节点的左子树节点值都不大于当前节点值，右子树节点值都不小于当前节点值。
基于这个性质，可以直接比较目标值与当前值，比随机二叉树找LCA快一些，相当于二分查找。

TreeNode* get_lca(TreeNode* root, int p, int q){
    if(root == NULL){
        return root;
    }
    left = root->val -p;
    right = root->val -q;
    if(left * right <= 0){ // p & q 分别分布在root左右子树，或者其中一个就是root
        return root;
    }
    if(left > 0){ // p & q 在root的同一侧，若left>0，表示都在左侧。
        return get_lca(root->left);
    }else{ // 否则都在右侧。
        return get_lca(root->right);
    }
}

非递归先序、中序遍历

放在一起，是因为两个实现方式几乎一样。
思路是，节点入栈，左节点入栈，直到左节点为空。然后节点出栈，右子树入栈。

vector<int> pre_traverse(TreeNode* root){
    vector<int> rs;
    if(root == NULL){
        return rs;
    }
    TreeNode* p = root;
    vector<TreeNode*> nodes;

    while(p != NULL || nodes.size() > 0){
        while(p != NULL){
            nodes.push_back(p);
            rs.push_back(p->val); // 放在这里是先序遍历
            p = p->left;
        }
        if(nodes.size()>0){
            p = nodes.back();
            nodes.pop_back();
            // rs.push_back(p->val); // 放在这里是中序遍历
            p = p->right;
        }
    }
    return rs;
}

非递归后序遍历

后序遍历比先序和中序稍微复杂一点儿。

vector<int> pre_traverse(TreeNode* root){
    vector<int> rs;
    if(root == NULL){
        return rs;
    }
    TreeNode* p, pre;
    vector<TreeNode*> nodes;
    nodes.push_back(root);

    while(nodes.size() > 0){
        p = nodes.back();
        if((p->left == NULL && p->right == NULL) || 
            (pre != NULL && (p->left == pre || p->right == pre))
            ){ // 这一行是精华，当p是叶子节点，或者p的左右孩子已经被遍历过了，那么p可以出栈了。
            rs.push_back(p->val);
            nodes.pop_back();
            pre = p;
        }else{
            if(p->right){
                nodes.push_back(p->right);
            }
            if(p->left){
                nodes.push_back(p->left);
            }
        }
    }
    return rs;
}

层次遍历/计算树的深度

层次遍历借助一个队列实现，队列存储每一层的内容。
树的深度，非递归方法就是层次遍历。

vector<int> layer_traverse(TreeNode* root){
    vector<int> rs;
    if(root == NULL){
        return rs;
    }
    queue<TreeNode*> nodes;
    nodes.push(root);
    TreeNode* p;
    // int depth = 0;

    while(nodes.size()>0){
        // depth ++; // 每进入一次，表示有一层，深度加一。
        int curlen = nodes.size(); // 这是当前层的长度。
        for(int i = 0; i < curlen; i++){
            p = nodes.front();
            nodes.pop();
            rs.push_back(p->val);
            if(p->left != NULL){
                nodes.push(p->left);
            }
            if(p->right != NULL){
                nodes.push(p->right);
            }
        }
    }
    return rs;
    // return depth;
}

计算树最浅/最深叶子节点的深度

先看最深的情况。递归版本很好实现。

int max_depth(TreeNode* root){
    if(root == NULL){
        return 0;
    }
    left_depth = max_depth(root->left);
    right_depth = max_depth(root->right);
    return (left_depth >= right_depth? left_depth: right_depth) + 1;
}

深度最浅的，得是非空叶子节点。

int min_depth(TreeNode* root){
    if(root == NULL){
        return 0;
    }
    if(root->left == NULL && root->right == NULL){
        return 1;
    }

    left_depth = min_depth(root->left);
    right_depth = min_depth(root->right);
    
    if(root->left == NULL){ // 左子树为空，只能去右边找了。
        return right_depth + 1;
    }

    if(root->right == NULL){
        return left_depth + 1;
    }

    return (left_depth <= right_depth? left_depth: right_depth) + 1;
}

水平翻转二叉树。

递归版本的核心是需要一个temp。

void horizon_reverse(TreeNode* root){
    if(root == NULL || (root->left == NULL && root->right == NULL)){
        return;
    }

    TreeNode* temp = root->right;
    root->right = horizon_reverse(root->left);
    root->left = horizon_reverse(temp);
}

非递归实现，借用层次遍历即可。

void horizon_reverse(TreeNode* root){
    if(root == NULL || (root->left == NULL && root->right == NULL)){
        return;
    }

    queue<TreeNode*> nodes;
    nodes.push(root);
    TreeNode* p;
    while(nodes.size()>0){
        int curlen = nodes.size();
        for(int i = 0; i < curlen; i++){
            p = nodes.front();
            nodes.pop();
            TreeNode* temp = p->left; // 不管左右子树是否为空，先进行交换。
            p->left = p->right;
            p->right = temp;
            if(p->left != NULL){
                nodes.push(p->left);
            }
            if(p->right != NULL){
                nodes.push(p->right);
            }

        }
    }
}

重建二叉树

不可能根据先序&后续重建二叉树，只有下面两种情况，实现起来也差不多。

根据先序&中序，构造二叉树
根据中序&后序，构造二叉树

中序序列必须出现，这样才能在先序或后序序列中找到左右节点的划分。
下面是根据先序和中序，重建二叉树，根据中序&后序的类似实现即可。

代码核心是：

先序的第一个节点是当前子树的根节点。
在中序list中找到根节点位置。

TreeNode* rebuild(vector<int> pre, vector<int> in, \
    int pre_start, int pre_end, int in_start, int in_end){
    if(in_start >= in_end){
        return;
    }
    TreeNode* root = new TreeNode(pre[pre_start]);

    int i = in_start;
    while(i <= in_end && in[i] != pre[pre_start]){
        ++i;
    }

    int new_left_in_end = i - 1;
    int left_tree_len = i - in_start;

    root->left = rebuild(pre, in, pre_start + 1, pre_start + left_tree_len, \
        in_start, new_left_in_end);
    root->right = rebuild(pre, in, pre_start + left_tree_len + 1, pre_end, \
        new_left_in_end + 2, in_end);

    return root;
}

// 入口
TreeNode* rebuild_enter(vector<int> pre, vector<int> in){
    rebuild(pre, in, 0, pre.size() - 1, in.size() - 1);
}

path sum i

求树中满足和为指定数的路径。

第一种情况，判断是否有满足条件的路径即可。
实现很简洁。

bool has_path_sum(TreeNode* root, int sum){
    if(root == NULL){
        return false;
    }
    if(root->left == NULL && root->right == NULL && root->val == sum){
        return true;
    }
    return has_path_sum(root->left, sum - root->val) || \
        has_path_sum(root->right, sum - root->val);
}

第二种情况，返回任意一条满足条件的路径。（若没有，路径为空）。
需要一个vector保存路径，找到一条路径return即可。

vector<TreeNode*> path_sum_start(TreeNode* root, int sum){
    vector<TreeNode*> path;
    return path_sum(root, sum, path);
}

vector<TreeNode*> path_sum(TreeNode* root, int sum, vector<TreeNode*> path){
    if(root == NULL){
        return;
    }
    
    path.push_back(root);
    if(root->left == NULL && root->right == NULL){ //叶子节点，路径终点。
        if(root->val == sum){ // 
            return path;
        }
    }

    if(path_sum(root->left, sum - root->val, path) || \
        path_sum(root->right, sum - root->val, path)){
        return path;
    }

    path.pop_back();

    // 否则就是没有匹配的路径，返回空。
}

path sum ii

求树中满足和为指定数的路径，保留下全部路径。

vector<vector<TreeNode*>> path_sum_start(TreeNode* root, int sum){
    vector<vector<TreeNode*>> rs;
    vector<TreeNode*> path;
    path_sum(root, sum, rs, path);
    return rs;
}

void path_sum(TreeNode* root, int sum, \
    vector<TreeNode*> path, vector<vector<TreeNode*>> rs){
    if(root == NULL){
        return;
    }
    
    path.push_back(root);
    if(root->left == NULL && root->right == NULL && root->val == sum){ //找到了一条路径，保存下来。
        rs.push_back(path);
    }

    path_sum(root->left, sum - root->val, path, rs);
    path_sum(root->right, sum - root->val, path, rs);
    
    path.pop_back();
}

以上是入门款树的入门款题目。