date: 2020/01/19

基本概念

image.png


树结构定义

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };


144二叉树的前序遍历(中等)

中->左->右

https://leetcode-cn.com/problems/binary-tree-preorder-traversal

void preorder(TreeNode* root, vector<int> &result){
    if(root != NULL){
        result.push_back(root->val);   // !!!
        preorder(root->left, result);
        preorder(root->right, result);
    }
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    preorder(root, result);
    return result;
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    stack.push(root);
    while(!stack.empty()){
        // 取出栈顶
        root = stack.top();
        stack.pop();
        // 右结点先入栈(后访问)
        if(root->right != NULL)
            stack.push(root->right);
        // 左节点后入栈(先访问)
        if(root->left != NULL)
            stack.push(root->left);
        // 访问
        res.push_back(root->val);
    }
    return res;
}


094二叉树的中序遍历(中等)

左->中->右

https://leetcode-cn.com/problems/binary-tree-inorder-traversal

void inorder(TreeNode* root, vector<int> &result){
    if(root != NULL){
        inorder(root->left, result);
        result.push_back(root->val);   // !!!
        inorder(root->right, result);
    }
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorder(root, result);
    return result;
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    do{
        // 找到以root为根的子树的最左节点
        while(root != NULL){
            stack.push(root);
            root = root->left;
        }
        // 以root为根的子树的最左节点如果存在
        if(!stack.empty()){
            // 弹出栈顶
            root = stack.top();
            stack.pop();
            // 访问
            res.push_back(root->val);
            // 进入右结点
            root = root->right;
        }
    }while(root != NULL || !stack.empty());
    // 返回结果
    return res;
}


145二叉树的后序遍历(困难)

左->右->中——这个访问顺序不易实现,需要记录已访问的节点

反序遍历(中->右->左)+翻转结果是一种作弊解法,并不是真正意义上的后序遍历

https://leetcode-cn.com/problems/binary-tree-postorder-traversal

可以与前序遍历比较一下——

  1. 每次循环取出栈顶的时候不直接出栈,只有左右节点都访问过了才能出栈
  2. 如果左/右节点未访问过,才会进入对应分支
  3. 只有左右节点都访问过了或者不存在,才能访问当前节点


void postorder(TreeNode* root, vector<int> &result){
    if(root != NULL){
        postorder(root->left, result);
        postorder(root->right, result);
        result.push_back(root->val);   // !!!
    }
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    postorder(root, result);
    return result;
}
// 可以根前序遍历比较一下
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    unordered_set<TreeNode*> visited;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    stack<TreeNode*> stack;
    stack.push(root);
    while(!stack.empty()){
        bool left_visited = true, right_visited = true;
        // 取出栈顶(但不弹出)
        root = stack.top();
        // 如果右结点未访问,则入栈(先入栈后访问)
        if(root->right != NULL && visited.find(root->right) == visited.end()){
            right_visited = false;
            stack.push(root->right);
        }
        // 如果左节点未访问,则入栈(后入栈先访问)
        if(root->left != NULL && visited.find(root->left) == visited.end()){
            left_visited = false;
            stack.push(root->left);
        }
        // 如果左右节点都访问过了,那么可以访问本节点
        if(left_visited && right_visited){
            visited.insert(root);
            res.push_back(root->val);
            stack.pop();
        }
    }
    return res;
}


102二叉树的层次遍历(中等)

https://leetcode-cn.com/problems/binary-tree-level-order-traversal

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    // 空树
    if(root == NULL)
        return res;
    // 开始遍历
    vector<TreeNode*> layer = {root}, tmp;
    while(!layer.empty()){
        vector<int> layer_res;
        // 处理当前层次的所有节点
        tmp.clear();
        for(int i = 0; i < layer.size(); i++){
            TreeNode* node = layer[i];
            // 访问
            layer_res.push_back(node->val);
            // 保存下一层次的节点
            if(node->left != NULL)
                tmp.push_back(node->left);
            if(node->right != NULL)
                tmp.push_back(node->right);
        }
        layer.swap(tmp);
        // 保存结果
        res.push_back(layer_res);
    }
    return res;


098验证二叉搜索树(中等)

https://leetcode-cn.com/problems/validate-binary-search-tree

class Solution {
private:
    const int UPPER_VALID = 0x01;
    const int LOWER_VALID = 0x10;
public:
    bool isValidBST(TreeNode* root, int lower, int upper, int flag = 0x00){
        // 递归终止条件:空节点
        if(root == NULL) return true;
        // 检查当前节点是否符合边界
        if((flag & UPPER_VALID) && root->val >= upper) return false;
        if((flag & LOWER_VALID) && root->val <= lower) return false;
        // 递归判断
        if(!isValidBST(root->left, lower, root->val, flag | UPPER_VALID)) return false;
        if(!isValidBST(root->right, root->val, upper, flag | LOWER_VALID)) return false;
        // 以root为根的树为有效的二叉搜索树
        return true;
    }

    bool isValidBST(TreeNode* root) {
        return isValidBST(root, 0, 0);
    }
};
bool isValidBST(TreeNode* root) {
    stack<TreeNode*> stack;
    TreeNode* node = root;
    long val = LONG_MIN;  // 因为node->val为int,所以初始的val必须能小于INT_MIN

    while(node != NULL || !stack.empty()){
        // 以node为根的子树的最左节点
        while(node != NULL){
            stack.push(node);
            node = node->left;
        }
        node = stack.top();
        stack.pop();
        // 判断是否符合条件
        if(node->val <= val) return false;
        // 保留值,进入右子树
        val = node->val;
        node = node->right;
    }
    return true;
}


236二叉树的最近公共祖先(简单)

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 终止条件
    if(root == NULL || root == p || root == q)
        return root;
    // 分别搜索左右分支
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    // 如果其中一个分支搜索结果为空,那公共祖先肯定在另一个分支上
    if(left == NULL)
        return right;
    else if(right == NULL)
        return left;
    else    // 如果两个分支搜索结果都不为空,那根节点就是公共祖先
        return root;
}
// 先序遍历
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == NULL)
        return NULL;
    // 开始遍历
    bool match_one = false;
    TreeNode* node;   // 当前节点
    unordered_map<TreeNode*, TreeNode*> parents;  // node -> parent
    unordered_set<TreeNode*> ancestors;  // p或q的祖先集合
    stack<TreeNode*> stack;
    stack.push(root);
    while(!stack.empty()){
        // 取出栈顶
        node = stack.top();
        stack.pop();
        // 访问
        if(node == p || node == q){
            if(match_one){  // 已经见过p或q,ancestors集合是有效的
                // 找到共同的祖先
                for(TreeNode* n = node; n != root; n = parents[n]){
                    if(ancestors.find(n) != ancestors.end())
                        return n;
                }
                return root;
            }else{  // 第一次见到p或q,收集其祖先节点
                match_one = true;
                for(TreeNode* n = node; n != root; n = parents[n])
                    ancestors.insert(n);
            }
        }
        // 左右节点入栈,记录父节点
        if(node->right != NULL){
            parents[node->right] = node;
            stack.push(node->right);
        }
        if(node->left != NULL){
            parents[node->left] = node;
            stack.push(node->left);
        }

    }
    return NULL;
}


235二叉搜索树的最近公共祖先(简单)

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

236二叉搜索树的最近公共祖先 的一个特殊情况,由于二叉搜索树的左子树所有节点均小于当前节点、右子树所有节点均大于当前节点——所以并不一定需要搜索每棵子树

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 终止条件
    if(root == NULL || root == p || root == q)
        return root;
    // 分别搜索左右分支
    TreeNode *left = NULL, *right = NULL;
    if(p->val < root->val || q->val < root->val)
        left = lowestCommonAncestor(root->left, p, q);
    if(p->val > root->val || q->val > root->val)
        right = lowestCommonAncestor(root->right, p, q);
    // 如果其中一个分支搜索结果为空,那公共祖先肯定在另一个分支上
    if(left == NULL)
        return right;
    else if(right == NULL)
        return left;
    else    // 如果两个分支搜索结果都不为空,那根节点就是公共祖先
        return root;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while(root != NULL){
        if(root->val > p->val && root->val > q->val)  // 均小于当前节点,说明都在左支
            root = root->left;
        else if(root->val < p->val && root->val < q->val) // 均大于当前节点,说明都在右支
            root = root->right;
        else   // 一大一小,说明是分割节点;或其中一个刚好等于当前节点,因为是由浅入深的搜索,所以另一节点必定是该节点的子孙节点
            return root;
    }
    return NULL;
}


"104二叉树的最大深度(简单)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#gAId7


"111二叉树的最小深度(简单)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#vhyKx


面试题07重建二叉树

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof   

“重(zhong)建(jian)二(er)叉(cha)树(shu)”笑死~


已知前序遍历序列 pre=[3,9,20,15,7] ,中序遍历序列 in=[9,3,15,20,7] ,构建二叉树

  1. 由于前序遍历是“中->左->右”,显然 pre 第一个元素 3 为根节点
  2. in 中找到元素 3 的位置,由于中序遍历是“左->中->右”,那么显然 3 左侧的子序列 [9] 是左子树的中序遍历序列,右侧的子序列 [15, 20, 7] 是右子树的中序遍历序列
  3. 既然左右子树的结点数量都已知(分别是1和3),而前序遍历是“中->左->右”,那么左子树的前序遍历序列为 [9] ,右子树前序遍历序列为 [20, 15, 7] 
  4. 也就是说,问题被分解为两个子问题:
    1. 已知前序遍历序列 [9] ,中序遍历序列 [9] ,构建左子树
    2. 已知前序遍历序列 [20, 15, 7] ,中序遍历序列 [15, 20, 7] ,构建右子树

然后以 3 为根节点,合并两棵子树——显然是一个递归问题:空间O(n)时间O(n)

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, 
                    int pre_start, int pre_end, int in_start, int in_end) {
    if(pre_start >= pre_end || in_start >= in_end)
        return NULL;
    TreeNode* root = new TreeNode(preorder[pre_start]);
    for(int i = 0; i < in_end - in_start; i++){
        if(preorder[pre_start] == inorder[in_start + i]){
            root->left = buildTree(preorder, inorder, 
                                   pre_start + 1, pre_start + i + 1, 
                                   in_start, in_start + i);
            root->right = buildTree(preorder, inorder, 
                                    pre_start + i + 1, pre_end, 
                                    in_start + i + 1, in_end);
            break;
        }
    }
    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return buildTree(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}


剑指-二叉搜索树的后序遍历序列

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

image.png

搜索二叉树:对于每个二叉树节点,它的所有左子树节点均小于自己,它的所有右子树节点均大于自己

后序遍历:左子树 -> 右子树 -> 根节点

显然一个二叉搜索树的后序遍历序列将被分为三部分——左子树的后序遍历序列,右子树的遍历序列,根节点。序列最后一个元素即根节点,那么将其作为分界点,可以找到序列中左右子树的分界点(同时左子树的所有元素必须小于该节点,右子树所有元素必须大于该节点),然后继续递归判断左子树、右子树,直到处理完。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int>& sequence, int start, int end){
        if(start >= end)
            return true;
        int mid;
        for(mid = start; mid < end && sequence[mid] < sequence[end]; mid++);
        for(int i = mid; i < end; i++){
            if(sequence[i] < sequence[end])
                return false;
        }
        return VerifySquenceOfBST(sequence, start, mid - 1) && VerifySquenceOfBST(sequence, mid, end - 1);
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0)
            return false;
        if(sequence.size() == 1)
            return true;
        return VerifySquenceOfBST(sequence, 0, sequence.size() - 1);
    }
};