二叉树

基础知识

树首先最基础的就是遍历，前序遍历、中序遍历、后序遍历、BFS、DFS

前序遍历：根节点、前序遍历左子树、前序遍历右子树

中序遍历：中序遍历左子树、根节点、中序遍历右子树

后序遍历：左子树、右子树、根节点

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7

思路：首先根据遍历的基础知识，我们可以知道前序遍历：根、左子树、右子树，中序遍历：左子树、根、右子树。

问题中已经给出了前序和中序的结果，我们可以通过这两个结果来把根、左子树、右子树拆分、然后再循环这样的拆分从而重建树。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        //建立位置索引
        for(int i = 0; i < preorder.size(); i++){
            dic[inorder[i]] = i;
        }
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode *recur(int root, int left, int right){
        if(left > right){
            return nullptr;
        }
        TreeNode *node = new TreeNode(preorder[root]);
        int i = dic[preorder[root]];
        node->left = recur(root + 1, left, i - 1);
        node->right = recur(i-left + root + 1, i + 1, right);
        return node;
    }
};

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印

思路：这个问题就是对树的BFS遍历，一般利用队列来实现遍历，完成一层的遍历进入下一层时推出左子树的根节点然后遍历左子树，推出右子树的根节点遍历右子树。从而遍历整个树。

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> queue;
        if(root == nullptr){
            return ans;
        }
        queue.push(root);
        ans.push_back(root->val);
        while(!queue.empty()){
            TreeNode* node = queue.front();
            queue.pop();
            if(node->left != nullptr){
                queue.push(node->left);
                ans.emplace_back(node->left->val);
            }
            if(node->right != nullptr){
                queue.push(node->right);
                ans.emplace_back(node->right->val);
            }
        }
        return ans;
    }
};

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构，即 A中有出现和B相同的结构和节点值。

思路：判断是不是子结构首先要找到相同的根节点，这个时候我们可以构建一个函数来判断两个树的节点是否一样，如果一样就进行匹配，不一样的话就向下寻找相同的节点再进行匹配。

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == nullptr || B == nullptr){
            return false;
        }
        return recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
private:
    bool recur(TreeNode* A, TreeNode* B){
        if(B == nullptr){
            return true;
        }
        if(A == nullptr || A->val != B->val){
            return false;
        }
        return recur(A->left, B->left) && recur(A->right, B->right);
    }
};

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

思路：首先二叉搜索树通过中序遍历可以形成一个递增序列，这里用dfs进行遍历即可，由于我们要形成循环双向链表，所以我们必须要一个头节点，和一个前驱节点用来保存，最后再将头节点和前驱节点连接起来

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr){
            return nullptr;
        }
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *head,*pre;
    void dfs(Node* root){
        if(root == nullptr){
            return ;
        }
        dfs(root->left);
        if(pre != nullptr){
            pre->right = root;
        }else{
            head = root;
        }
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};

剑指 Offer 34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

思路：这一题比较常规，就是用dfs把节点的值减去，一直向下记录路径，满足要求的结果存入res中，最后向上回溯的时候剔除当前节点。

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return res;

    }
    void dfs(TreeNode* cur, int target){
        if(cur != nullptr){
            target = target - cur->val;
            path.push_back(cur->val);
            if(target != 0 || cur->left != nullptr || cur->right != nullptr){
                dfs(cur->left, target);
                dfs(cur->right, target);
            }else{
                res.push_back(path);
            }
            path.pop_back();
        }
    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同

思路：首先是给我们一个二叉搜索树的后序遍历结果，后序遍历是左子、右子、根的排列，又因为二叉搜索树的左子树一定小于根节点，右子树一定大于根节点，所以我们可以用递归的方式将数组一步步的拆分，并在其中加入判断条件，如果拆分为右子树的部分的值小于根节点，则说明不是搜索树后序遍历的结果。

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