剑指 offer 二叉树题目汇总（C++版）
 
先回顾二叉树的各种遍历算法再阅读本文效果更佳，
传送门：二叉树遍历算法总结（递归+非递归）
 

1、二叉树的镜像
输入一个二叉树，该函数输出它的镜像。
举例：

思路1：递归
对于样例来说，先改变根结点8的左指针指向的值，左边指向的值换到右边，右边指向的值换到左边。
接下来，递归处理，将左子树的根结点作为新的 root，进行上面相同的操作。右子树同理。
时间复杂度：O(n) 空间复杂度：O(n)

TreeNode* Mirror(TreeNode* pRoot) {
       if(!pRoot) return pRoot; //特判：如果pRoot为空，返回空
       swap(pRoot->left, pRoot->right);
       Mirror(pRoot->left);
       Mirror(pRoot->right);
       return pRoot;
}

思路2：使用队列或者栈 ,利用队列遍历树的每一个节点，并交换节点的左右儿子节点
时间和空间复杂度同上

TreeNode* Mirror(TreeNode* pRoot) {
        if(!pRoot) return pRoot;
        queue<TreeNode*> q;
        q.push(pRoot);
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            swap(t->left, t->right);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return pRoot;
}

2、对称的二叉树
实现一个函数，判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路1：递归
时间复杂度：O(n) 空间复杂度：O(n)

bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return judge(root->left,root->right);
    }
    
 bool judge(TreeNode* p,TreeNode* q) {
        if(!p && !q) return true;  //所有节点都已比较完成，返回true
        if(!p || !q || p->val != q->val) return false;  //如果当前对应节点有缺失的或者节点值不相等，返回false
        return judge(p->left,q->right) && judge(p->right,q->left); //递归判断下一组对应节点
    }

思路2：利用队列遍历树的每一个节点，并保存成对的节点
1.出队时也是成对的

• 若都为空，继续；
• 一个为空，返回false;
• 不为空，比较当前值，值不等，返回false；

2.确定入队顺序，每次入队都是成对的，如left.left， right.right ;left.rigth,right.left

时间复杂度：O(n) 空间复杂度：O(n)

bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(q.size()) {
            auto left=q.front();
            q.pop();
            auto right=q.front();
            q.pop();
            if(!right && !left) continue;  //nullptr 也会入队
            if(!right || !left) return false;
            if(right->val != left->val) return false;
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }

3、不分行从上向下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
思路：使用队列对对二叉树进行层序遍历
时间复杂度：O(n) 空间复杂度：O(n)

vector<int> levelOrder(TreeNode* root) {
        vector<int> v;
        if(!root) return v;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            auto t = q.front();
            q.pop();
            v.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        return v;
    }

4、分行上向下打印二叉树
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
思路：使用队列对对二叉树进行层序遍历，记录每一层遍历到的节点
时间复杂度：O(n) 空间复杂度：O(n)

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            int n = q.size();
            vector<int> v;
            for(int i=0;i<n;i++) {
                 auto t = q.front();
                 q.pop();
                 v.push_back(t->val);
                 if(t->left) q.push(t->left);
                 if(t->right) q.push(t->right);
            }
            res.push_back(v);
        }
        return res;
    }

5、之字打印二叉树
第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
思路：跟上一题一样使用队列，只不过是存储的时候需要翻转一下当前层的结果。改造一下上一题代码即可
时间复杂度：O(n) 空间复杂度：O(n)

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        bool flag = true;
        while(q.size()) {
            int n = q.size();
            vector<int> v;
            for(int i=0;i<n;i++) {
                auto t = q.front();
                q.pop();
                v.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            if(!flag) reverse(v.begin(),v.end());
            flag = !flag;
            res.push_back(v);
        }
        return res;
    }

6、二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
思路1：递归，根节点加上左右子树的最大深度就是树的最大深度
时间复杂度：O(n) 空间复杂度：O(n)

int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left),maxDepth(root->right)) + 1;
    }

思路2：使用队列，二叉树的层序遍历，有多少层深度就是多少
时间复杂度：O(n) 空间复杂度：O(n)

int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            int n = q.size();
            for(int i = 0;i < n;i++) {
                auto t = q.front();
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            depth++;
        }
        return depth;
    }

7、平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
平衡二叉树具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
思路：这不就利用上了求二叉树深度的代码了么
时间复杂度：O(n) 空间复杂度：O(n)

bool isBalanced(TreeNode* root) {
        if(!root) return true;
         //左右子树高度差不大于1且左右子树都是平衡二叉树
        return abs(depth(root->left) - depth(root->right)) <= 1 &&
               isBalanced(root->left) && isBalanced(root->right);
    }
 
 //求二叉树深度 
 int depth(TreeNode* root) {
        if(!root) return 0;
        return max(depth(root->left),depth(root->right))+1;
    }

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

• 首先判断两个二叉树为空的情况，如果为空，直接return false
• 如果不为空，就可以调用isPart(A, B)函数来判断B是否为A的子树。如果不是，则递归，判断B是否是A的左子树的子树，或者，B是否是A的右子树的子树
• 对于函数isPart(A, B)，首先判断B子树的节点是否为空，如果为空，说明前面的都匹配，直接return true
• 如果B树的节点不为空，但是A树的节点为空，那么不匹配，return false
• 如果A和B树的节点都不为空，但是值不一样，也是不匹配，return false
• 最后如果 B 树的节点不为空，A树的节点也不为空，A树和B树的当前节点是匹配的。那么我们就递归到A和B的左子树，同时，A和B的右子树，看看是否匹配，注意这里是&&

时间复杂度：O(n) 空间复杂度：O(n)

bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;
        if(isPart(A,B)) return true;
        return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }

bool isPart(TreeNode*A,TreeNode* B) {
       if(!B) return true;
       if(!A) return false;
       if(A->val != B->val) return false;
       return isPart(A->left,B->left) && isPart(A->right,B->right);
   }

9、二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如下面这棵树，节点 2 和节点 8 的最近公共祖先是 6，节点 2 和节点 4 的最近公共祖先是 2。

思路：题目给了树是二叉搜索树，那么必然会用到其性质，即根节点值大于左儿子且小于右儿子。该题的要点就是要判断出给定的两个节点的位置分布情况。不难发现，如果给定的两个节点位于根的左右两边，那么根就是其最近公共祖先。否则两个节点一定会同时位于根的左侧或者右侧，此时再去递归判断左子树或者右子树即可。

时间复杂度：O(n) 空间复杂度：O(n)

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;
        if(root->val > p->val && root->val > q->val) {
            //说明两个节点都在左子树
            return lowestCommonAncestor(root->left,p,q);
        }
        if(root->val < p->val && root->val < q->val) {
            //说明两个节点都在右子树
            return lowestCommonAncestor(root->right,p,q);
        }
      
        return root; //两个节点在根的两侧
    }

10、二叉树的最近公共祖先
给定一个二叉树（非二叉搜索树）, 找到该树中两个指定节点的最近公共祖先。
思路：其实本质与上一题是一样的，核心就是判断出给定的两个节点相对于根节点的分布位置。
时间复杂度：O(n) 空间复杂度：O(n)

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;
        if(root == p || root == q) return root;
        //分别去左右子树里面找
        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);
        //p，q各在一边，当前根就是最近共同祖先 
        if(left && right) return root; 
        if(left) return left;  //p，q都在左子树
        if(right) return right;   //p，q都在右子树
        return nullptr;
    }

11、二叉搜索树的第K个节点
给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的结点。
思路：因为是二叉搜索树，所以中序遍历的结果就是从小到大排序的，边遍历边记录，取第k个就可以了
时间复杂度：O(n) 空间复杂度：O(n)

TreeNode* KthNode(TreeNode* pRoot, int k) {
        if (!pRoot) return pRoot;
    stack<TreeNode*> s;
    int i = 0;
    auto cur = pRoot;
    while (cur || s.size()) {
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }
        i++;
        auto t = s.top();
        s.pop();
        if (i == k) return t;
        cur = t->right;
    }
    return nullptr;
    }

思考：如果题目要求第k大的节点呢？
 
12、二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
思路：递归。后序遍历序列中最后一个节点即为根节点，树是二叉搜索树，因此可以将序列根据根节点分成左右子树，左子树节点值都小于根节点，右子树的节点值都大于根节点，同时左右子树也满足上述性质。
时间复杂度：O(n) 空间复杂度：O(n)

bool verifyPostorder(vector<int>& postorder) {
        if(!postorder.size()) return true;
        return judge(postorder,0,postorder.size()-1);
    }

    bool judge(vector<int>& a,int l,int r) {
        if(l>=r) return true; //l=r是叶子节点，l>r是空树，两者都是true
        int i = l;
        while(i < r && a[i]<a[r]) i++; //找到第一个大于根的节点
        //判断右子树所有节点是否合规
        for(int j=i;j<r;j++) {
            if(a[j]<a[r]) return false;
        }
        //递归判断左右子树
        return judge(a,l,i-1) && judge(a,i,r-1);
    }

思考：是否可以判断二叉树的前序遍历序列呢？

13、二叉树中和为某一值得路径
给二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
举例：
targetSum = 22
输出：[ [5,4,11,2],[5,8,4,5] ]

思路：递归，用深度优先 DFS 搜索，需要用到二维的 vector，每当搜索到新结点时，都要记录该结点。而且每当找出一条路径之后，都将这个保存为一维 vector 的路径 push 到结果二维 vector 中。此外，每当 DFS 搜索到子结点，发现不是路径和时，返回上一个结点时，需要把该结点从一维 vector 中移除
时间复杂度：O(n) 空间复杂度：O(n)

vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(!root) return {};
        vector<vector<int>> res;
        vector<int> path;
        dfs(root,target,path,res);
        return res;
    }

     void dfs(TreeNode* root, int sum,vector<int> path,vector<vector<int>> &res) {
        if(!root) return;
        sum -= root->val;
        path.push_back(root->val);
        if(!root->left && !root->right && !sum) res.push_back(path);
        dfs(root->left,sum,path,res);
        dfs(root->right,sum,path,res);
        path.pop_back();
    }

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

上面的树转化成双向循环链表。链表中的每个节点都有一个前驱和后继指针。链表第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

转化后的链表长这样。“head” 表示指向链表中有最小元素的节点。转化完成以后，树中节点的左指针要指向前驱，树中节点右指针要指向后继。返回链表中的第一个节点的指针。

思路1：递归，用二叉搜索树的性质，左<根<右，对树进行中序遍历，遍历过程中把相邻的结点连接起来，此时要知道上一个遍历到的结点是什么，用一个变量 pre 记录上一个遍历到的结点。还需要一个变量 head 记录最左结点。在递归函数中，先判空，之后对左子结点调用递归，此时会先一直递归到最左结点，如果 head 为空，说明当前就是最左结点，赋值给 head 和 pre，对于之后的遍历到的结点，那就可以和 pre 相互连接，然后 pre 赋值为当前遍历到的结点 node，接着再对右子结点调用递归即可
时间复杂度：O(n) 空间复杂度：O(n)

Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        Node* pre = nullptr,*head = nullptr;
        Inorder(root,pre,head);
        head->left = pre; //最后把首尾连上
        pre->right = head;
        return head;
    }

    //中序遍历
    void Inorder(Node* node, Node* &pre, Node* &head) {
        if(!node) return;
        Inorder(node->left,pre,head);
        if(!head) { //找到最左子节点
            head = node;
            pre = node;
        } else { //相互连接形成双线链表
            pre->right = node; 
            node->left = pre;
            pre = node;
        }
        Inorder(node->right,pre,head);
    }

思路2：中序遍历当然可以用迭代来写啦，思路上面相同，直接上代码
时间复杂度：O(n) 空间复杂度：O(n)

Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        Node* pre = nullptr,*head = nullptr;
        stack<Node*> s;
        auto cur = root;
        while(cur || s.size()) {
            while(cur) {
                s.push(cur);
                cur = cur->left;
            }
            auto t = s.top();
            s.pop();
            if(!head) head = t;
            if(pre) {
                pre->right = t;
                t->left = pre;
            }
            pre = t;
            cur = t->right;
        }

        head->left = pre;
        pre->right = head;
        return head;
    }

15、重建二叉树
输入二叉树的前序遍历和中序遍历的结果，构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
思路：递归，前序遍历序列第一个数是根节点，我们用这个根节点在中序遍历序列中找到其所在位置下标，位于下标左边的就是左子树的节点，位于下标右边的就是右子树的节点，这样就可以利用该性质递归构造出二叉树了。
时间复杂度：O(n) 空间复杂度：O(n)

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(!preorder.size() || !inorder.size()) return nullptr;
        auto root = new TreeNode(preorder[0]);//创建根节点
        int rootIndex = 0;
        //找到根节点的索引位置
        for(int i = 0;i < inorder.size();i++) {
            if(inorder[i] == preorder[0]) {
                rootIndex = i;
                break;
            }
        }
       //前序和中序遍历的左右子树数组
        vector<int> preLeft,preRight,inLeft,inRight;
        for(int i = 0;i < rootIndex;i++) {
            preLeft.push_back(preorder[i+1]);
            inLeft.push_back(inorder[i]);
        }

        for(int i = rootIndex+1;i < preorder.size();i++) {
            preRight.push_back(preorder[i]);
            inRight.push_back(inorder[i]);
        }

        //递归创建左右子树
        root->left = buildTree(preLeft,inLeft);
        root->right = buildTree(preRight,inRight);

        return root;
    }

16、二叉树的序列化和反序列化
请实现两个函数，分别用来序列化和反序列化二叉树。
设计一个算法来实现二叉树的序列化与反序列化。不限定序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

string serialize(TreeNode* root) {
        string res;
        dfs1(root,res);
        return res;
    }

    TreeNode* deserialize(string data) {
        int u = 0;
        auto root = dfs2(data,u);
        return root;
    }
    
    //序列化二叉树
    void dfs1(TreeNode* root,string &res) {
        if(!root) {
            res += "#,";//当前节点为空则保留一个#号和一个逗号
            return;
        }
        res += to_string(root->val) + ','; //不为空则保留当前节点值和一个逗号
        dfs1(root->left,res);
        dfs1(root->right,res);
    }

    //反序列化二叉树
    TreeNode* dfs2(string data,int &u) {
        if(data[u] == '#') {
            u += 2; //u用来保存当前的字符串遍历的位置，跳过#号和逗号 
            return nullptr; //表示本次构造的是一个null节点，没有孩子节点，跳过后面的递归
        }
        int t = 0; //用来记录当前节点的值
        bool flag = false; //记录正负
        if(data[u] == '-') {
            u += 1;  //跳过负号
            flag = true;
        }
        while(data[u] != ',') {  //计算当前节点值
            t = t*10 + data[u] - '0';
            u++;
        }
        u++;   //跳过逗号
        if(flag) {   //负数处理
            t = -t;
            flag = !flag;
        }
        //构造根节点以及左右孩子节点
        auto root = new TreeNode(t); 
        root->left = dfs2(data,u);
        root->right = dfs2(data,u);

        return root; //返回根节点
    }