「算法刷题」二叉树专题汇总（力扣版）

本文记录作者刷题过程中与二叉树相关的题目。

一、深度优先遍历

144. 二叉树的前序遍历（简单难度）

方法一：递归遍历法

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        res.push_back(root->val);//前序位置插入
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
};

方法二：迭代遍历法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            res.push_back(cur->val);
            //右入栈
            if(cur->right) stk.push(cur->right);
            //左入栈
            if(cur->left) stk.push(cur->left);
        }
        return res;
    }
};

方法三：分治思想

class Solution {
public:
    // 定义：输入二叉树，返回其前序遍历数组
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        // 获取左、右子树的前序遍历数组
        vector<int> leftRes=preorderTraversal(root->left);
        vector<int> rightRes=preorderTraversal(root->right);
        // 一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
        res.push_back(root->val);
        res.insert(res.end(),leftRes.begin(),leftRes.end());
        res.insert(res.end(),rightRes.begin(),rightRes.end());
        return res;
    }
};

94. 二叉树的中序遍历（简单难度）

方法一：递归法

class Solution {
private:
    vector<int> res;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
        return res;
    }
};

方法二：迭代法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        TreeNode* cur=root;
        while(cur||!stk.empty()){
            // 存在
            if(cur){
                stk.push(cur);//入栈
                cur=cur->left;//换左边
            }
            // 不存
            else{
                cur=stk.top();//出栈
                stk.pop();
                // 处理节点
                res.push_back(cur->val);
                cur=cur->right;//换右边
            }
        }
        return res;
    }
};

145. 二叉树的后序遍历

方法一：递归法

class Solution {
private:
    vector<int> res;
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

方法二：迭代法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            res.push_back(cur->val);
            //左入栈
            if(cur->left) stk.push(cur->left);
            //右入栈
            if(cur->right) stk.push(cur->right);
        }
        reverse(res.begin(), res.end());// 反向
        return res;
    }
};

589. N 叉树的前序遍历（简单难度）

class Solution {
private:
    vector<int> res;
public:
    vector<int> preorder(Node* root) {
        if(root==nullptr) return res;
        res.push_back(root->val);
        for(Node* node:root->children)
            preorder(node);
        return res;
    }
};

590. N 叉树的后序遍历（简单难度）

class Solution {
private:
    vector<int> res;
public:
    vector<int> postorder(Node* root) {
        if(root==nullptr) return res;
        for(Node* node:root->children)
            postorder(node);
        res.push_back(root->val);
        return res;
    }
};

114. 二叉树展开为链表（中等难度）

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* pre=nullptr;
        if(root==nullptr) return ;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            if(pre) pre->right=cur;
            pre=cur;
            //右入栈
            if(cur->right) stk.push(cur->right);
            //左入栈
            if(cur->left) stk.push(cur->left);
        }
        pre=root;
        while(pre){
            pre->left=nullptr;
            pre=pre->right;
        }
    }
};

方法二：

class Solution {
public:
    vector<TreeNode*> arr;
    void flatten(TreeNode* root) {
        dfs(root);
        for(int i=1;i<arr.size();++i){
            arr[i-1]->right=arr[i];
            arr[i-1]->left=nullptr;
            arr[i]->left=nullptr;
        }
    }
    void dfs(TreeNode* root){
        if(root==nullptr) return;
        arr.push_back(root);
        dfs(root->left);
        dfs(root->right);
    }
};

二、广度优先遍历

面试题32 - I. 从上到下打印二叉树（中等难度）

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(root==NULL) return res;
        // 先入队 
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            // 出队
            TreeNode* cur=que.front();
            que.pop();
            // 处理节点
            res.push_back(cur->val);
            // 入队
            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
        return res;
    }
};

102. 二叉树的层序遍历（中等难度）

剑指 Offer 32 - II. 从上到下打印二叉树 II（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result;
    }
};

107. 二叉树的层序遍历 II（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

剑指 Offer 32 - III. 从上到下打印二叉树 III（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        bool isReverse=false;
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            if(isReverse) reverse(level_result.begin(),level_result.end());
            isReverse = !isReverse;
            result.push_back(level_result);
        }
        return result;
    }
};

429. N 叉树的层序遍历（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<Node*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                Node* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                for(Node* node:cur->children){
                    if(node)   queue.push(node);
                }
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result;
    }
};

103. 二叉树的锯齿形层序遍历（中等难度）

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==nullptr) return res;
        bool flag=false;
        queue<TreeNode*>  que;
        que.push(root);
        while(!que.empty()){
            vector<int> level;
            int size=que.size();
            for(int i=0;i<size;++i){
                // 出栈
                TreeNode* cur=que.front();
                que.pop();
                // 处理
                level.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            if(flag)reverse(level.begin(), level.end());
            flag=!flag;
            res.push_back(level);
        }
        return res;
    }
};

199. 二叉树的右视图（中等难度）

剑指 Offer II 046. 二叉树的右侧视图（中等难度）

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result.back());
        }
        return result;
    }
};

515. 在每个树行中找最大值（中等难度）

剑指 Offer II 044. 二叉树每层的最大值（中等难度）

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            int level_max=INT_MIN;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_max=max(level_max,cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_max);
        }
        return result;
    }
};

513. 找树左下角的值（中等难度）

剑指 Offer II 045. 二叉树最底层最左边的值（中等难度）

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return -1;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result.back()[0];
    }
};

637. 二叉树的层平均值（简单难度）

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            double level_sum=0.0;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_sum+=cur->val;
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_sum/size);
        }
        return result;
    }
};

116. 填充每个节点的下一个右侧节点指针（中等难度）

117. 填充每个节点的下一个右侧节点指针 II（中等难度）

class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL) return root;
        //先入队
        queue<Node*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            //vector<int> level_result;
            Node* pre=NULL;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                Node* cur=queue.front();
                queue.pop();
                //处理节点
                if(pre) pre->next=cur;
                pre=cur;
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
        }
        return root;
    }
};

662. 二叉树最大宽度（中等难度）

class Solution {
public:
    /*空节点下还可以挂载空节点,无法通过常规的层序遍历来为空节点保留子节点
    给每个节点添加一个编号，通过编号来记录每层的宽度，但是这个编号可能会非常大
    由于官方更新了测试用例，导致用原本二叉树的val记录编号（int型）会造成溢出。*/
    int widthOfBinaryTree(TreeNode* root) {
        int res=0;
        queue<pair<TreeNode *, long long>> que; //队列记录二叉树的结点和一个对应的long long型编号
        if(root==nullptr) return res;
        que.push(make_pair(root, 0)); //根节点入队，并记录对应编号
        while(!que.empty()){
            int size=que.size();
            int start = 0, end = 0;
            // 从左到右遍历每一行
            for(int i=0;i<size;++i){
                // 出队
                TreeNode* curNode = que.front().first;
                long long curId = que.front().second;
                que.pop();
                // 记录当前行第一个和最后一个节点的编号
                if (i == 0) start = curId;
                if (i == size - 1) end = curId;
                curId -= start; //缩小编号索引，以每层第一个结点的值为偏移值，保持每层结点之间的相对关系，缩小索引
                // 入队
                if(curNode->left) que.push(make_pair(curNode->left, curId*2));
                if(curNode->right) que.push(make_pair(curNode->right, curId*2+1));
            }
            res=max(res, (int)(end-start+1));
        }
        return  res;
    }
};

958. 二叉树的完全性检验（中等难度）

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> que; 
        que.push(root); 
        bool end=false;// 是否遍历完所有的非空节点
        while(!que.empty()){
            int size=que.size();
            // 从左到右遍历每一行
            for(int i=0;i<size;++i){
                // 出队
                TreeNode* curNode = que.front();
                que.pop();
                // 第一次遇到null时end变成true，
                //如果之后的所有节点都是 null，则说明是完全二叉树
                if(curNode==nullptr) end = true;
                else{
                    // end为 true时遇到非空节点说明不是完全二叉树
                    if (end) return false;
                    // 入队
                    que.push(curNode->left);
                    que.push(curNode->right);
                }
            }
        }
        return  true;
    }
};

三、从数组中构造二叉树

654. 最大二叉树（中等难度）

问题：

给定一个不重复的整数数组 nums ，返回 nums 构建的 最大二叉树 :

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

点评

分治思想：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums,0,nums.size()-1);
    }
    // 定义：从数组的[start,end]区间构建最大二叉树
    TreeNode* dfs(vector<int>& nums,int start,int end){
        if(start>end) return nullptr;
        // 获取最大值索引
        int max_index=start;
        for(int i=start+1;i<=end;++i){
            if(nums[i]>nums[max_index]) max_index=i;
        }
        // 构建二叉树
        TreeNode* root=new TreeNode(nums[max_index]);
        if(start==end) return root;//加上更加高效，终止条件
        root->left=dfs(nums,start,max_index-1);
        root->right=dfs(nums,max_index+1,end);
        return root;
    }
};

105. 从前序与中序遍历序列构造二叉树（中等难度）

剑指 Offer 07. 重建二叉树（中等难度）

问题：

点评

写法一：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //从先序数组找切割点对应的值
        if (preorder.size() == 0) return NULL;//终止条件1
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);//
        if (preorder.size() == 1) return root;//终止条件2
        //寻找中序数组的切割点
        int Index;
        for (Index = 0; Index < inorder.size(); Index++) {
            if (inorder[Index] == rootValue) break;
        }
    	//切割中序数组
        vector<int> leftInorder(inorder.begin(), inorder.begin() + Index);
        vector<int> rightInorder(inorder.begin() + Index + 1, inorder.end() );
        //寻找先序数组的切割点
    	Index = leftInorder.size();//长度相同
        preorder.erase(preorder.begin());//删除第一个元素
        //切割先序数组
    	vector<int> leftPreorder(preorder.begin(), preorder.begin() + Index);
        vector<int> rightPreorder(preorder.begin() + Index, preorder.end());
        //递归调用左右子数组
        root->left = buildTree(leftPreorder,leftInorder);
        root->right = buildTree(rightPreorder,rightInorder);
        return root;
    }
};

写法二：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,0, preorder.size()-1,inorder,0,inorder.size()-1);
    }

    TreeNode* build(vector<int>& preorder,int preStart,int preEnd, vector<int>& inorder,int inStart,int inEnd) {
        if(preStart>preEnd) return nullptr;
        // 前序数组的第一个节点一定是根节点
        TreeNode* root=new TreeNode(preorder[preStart]);
        // 在中序数组找到根节点所在索引
        int index=0;
        for (int i = inStart; i <= inEnd; ++i) {
            if (inorder[i] == preorder[preStart]) {
                index = i;
                break;
            }
        }
        // 计算左子树长度
        int leftSize=index-inStart;
        root->left=build(preorder,preStart+1, preStart+leftSize,inorder,inStart,index-1);
        root->right=build(preorder,preStart+leftSize+1, preEnd,inorder,index+1,inEnd);
        return root;
    }
};

106. 从中序与后序遍历序列构造二叉树（中等难度）

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //从后序数组找切割点对应的值
        if (postorder.size() == 0) return NULL;//终止条件1
        int rootValue = postorder[postorder.size()-1];//最后一个元素
        TreeNode* root = new TreeNode(rootValue);
        if (postorder.size() == 1) return root;//终止条件2
        //寻找中序数组的切割点
        int Index;
        for (Index = 0; Index < inorder.size(); Index++) {
            if (inorder[Index] == rootValue) break;
        }
        //切割中序数组
        vector<int> leftInorder(inorder.begin(), inorder.begin() + Index);
        vector<int> rightInorder(inorder.begin() + Index + 1, inorder.end() );
        //寻找后序数组的切割点
        Index = leftInorder.size();//长度相同
        postorder.pop_back();//删除最后一个元素
        //切割后序数组
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + Index);
        vector<int> rightPostorder(postorder.begin() + Index, postorder.end());
        //递归调用左右子数组
        root->left = buildTree(leftInorder,leftPostorder);
        root->right = buildTree(rightInorder,rightPostorder);
        return root;
    }
};

剑指 Offer 37. 序列化二叉树（困难难度）

297. 二叉树的序列化与反序列化（困难难度）

二叉树的序列化：输入一个二叉树，输出其层序遍历输出的字符串

二叉树的反序列化：输入一个字符串，输出其构造的二叉树

点评

二叉树的序列化有先序、中序、后序和层序，但是二叉树的反序列化不支持中序遍历（无法确定根节点位置）。

基于先序遍历的序列化和反序列化：

//序列化
string serialize(TreeNode* root){
    string str="";
    dfs(root,str);
    return str;
}
void dfs(TreeNode* root,string& str){
    if(root==nullptr){
        str+="null,";
        return;
    }
    str+=to_string(root->val)+",";
    dfs(root->left,str);
    dfs(root->right,str);
}
// 反序列化
TreeNode* deserialize(string data){
    if(data.length()==0) return nullptr;
    // 切割字符串
    vector<string> str;
    stringstream ss(data);
    string t;
    while(getline(ss,t,',')){
        str.push_back(t);
    }
    // 构造二叉树
    return dedfs(str,0);
}
TreeNode* dedfs(vector<string>& nodes，int i){
    // 终止条件
    if(i>=nodes.size()) return nullptr;
    // 处理节点
    if(nodes[i]=="null") return nullptr;
    TreeNode* root=new TreeNode(stoi(nodes[i]));
    i++;
    // 递归搜索
    root->left=dedfs(nodes,i);
    root->right=dedfs(nodes,i);
    return root;
}

基于层序遍历的序列化和反序列化：

string serialize(TreeNode* root) {
    if(root==nullptr) return "";
    string res="";
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()){
        // 出栈
        TreeNode* cur=que.front();
        que.pop();
        // 处理
        if(cur==nullptr) res+="null,";
        else{
            res+=to_string(cur->val)+",";
            // 入栈
            que.push(cur->left);
            que.push(cur->right);
        } 
    }
    return res;
}
TreeNode* deserialize(string data) {
    if(data.length()==0) return nullptr;
    // 切割字符串
    vector<string> str;
    stringstream ss(data);
    string t;
    while(getline(ss,t,',')){
        str.push_back(t);
    }
    // 构建二叉树
    queue<TreeNode*> que;
    if(str[0]=="null") return nullptr;
    TreeNode* root=new TreeNode(stoi(str[0]));
    que.push(root);
    for(int i=1;i<str.size();){
        // 获取根节点
        TreeNode* cur=que.front();
        que.pop();
        // 添加左节点
        if(str[i]=="null") cur->left=nullptr;
        else{
            cur->left=new TreeNode(stoi(str[i]));
            que.push(cur->left);
        }
        ++i;
        // 添加右节点
        if(str[i]=="null") cur->right=nullptr;
        else{
            cur->right=new TreeNode(stoi(str[i]));
            que.push(cur->right);
        }
        ++i;
    }
    return root;
}

四、自顶向下遍历树

226. 翻转二叉树（简单难度）

剑指 Offer 27. 二叉树的镜像（简单难度）

问题：给你一棵二叉树的根节点 root ，水平翻转这棵二叉树，并返回其根节点。

点评

只要将二叉树的每个节点的左右子节点进行交换，就可以完全水平反转整个二叉树。

方法一：递归思想

单独抽出一个节点，需要让它把自己的左右子节点交换下

前中后序位置，似乎都可以

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        //终止条件
        if (root == NULL) return root;
        //处理节点
        swap(root->left, root->right); // 交换左右子节点
        //递归调用
        mirrorTree(root->left); // 左
        mirrorTree(root->right); // 右
        return root;
    }
};

方法二：分治思想

class Solution {
public:
    // 定义：输入二叉树，返回其前序遍历数组
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        // 获取左、右子树的前序遍历数组
        vector<int> leftRes=preorderTraversal(root->left);
        vector<int> rightRes=preorderTraversal(root->right);
        // 一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
        res.push_back(root->val);
        res.insert(res.end(),leftRes.begin(),leftRes.end());
        res.insert(res.end(),rightRes.begin(),rightRes.end());
        return res;
    }
};

100. 相同的树（简单难度）

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        //终止条件
        if(p==NULL&&q==NULL) return true;
        else if(p!=NULL&&q==NULL) return false;
        else if(p==NULL&&q!=NULL)return false;
        else if(p->val!=q->val)return false;
        //递归调用
        bool left=isSameTree(p->left,q->left);
        bool right=isSameTree(p->right,q->right);
        return left&&right;
    }
};

617. 合并二叉树（简单难度）

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //终止条件
        if(root1==NULL) return root2;
        if(root2==NULL) return root1;
    	//处理节点
        root1->val+=root2->val;
    	//递归调用
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }
};

101. 对称二叉树（简单难度）

剑指 Offer 28. 对称的二叉树（简单难度）

class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right){
        //终止条件
        if(left==NULL&&right==NULL) return true;
        else if(left!=NULL&&right==NULL)  return false;
        else if(left==NULL&&right!=NULL) return false;
        else if(left->val!=right->val) return false;
        //递归调用
        bool leftResult=compare(left->left,right->right);
        bool rightResult=compare(left->right,right->left);
        return leftResult&&rightResult;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        return compare(root->left,root->right);
    }
};

572. 另一棵树的子树（简单难度）

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)return true;
        else if(p!=NULL&&q==NULL) return false;
        else if(p==NULL&&q!=NULL) return false;
        else if(p->val!=q->val)return false;
        bool left=isSameTree(p->left,q->left);
        bool right=isSameTree(p->right,q->right);
        return left&&right;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == NULL && subRoot == NULL) return true;//LeetCode中没有设置该情况
        if (root == NULL && subRoot != NULL) return false;//LeetCode中没有设置该情况
        if (root != NULL && subRoot == NULL) return false;//LeetCode中没有设置该情况
        return isSameTree(root,subRoot)//root和subRoot相等
        ||isSubtree(root->left,subRoot)//subRoot是root的左子树的子树
        ||isSubtree(root->right,subRoot);//subRoot是root的右子树的子树
    }
};

剑指 Offer 26. 树的子结构（中等难度）

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)return true;//两个树的节点都为空，完全相等
        else if(p!=NULL&&q==NULL) return true;//p的节点不为空，q的节点为空，q全部匹配p
        else if(p==NULL&&q!=NULL) return false;//p的节点为空，q的节点不为空，p全部匹配q
        else if(p->val!=q->val)return false;// p和q的值不一样，p和q不匹配
        bool left=isSameTree(p->left,q->left);
        bool right=isSameTree(p->right,q->right);
        return left&&right;
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==NULL&&B==NULL) return false;
        if(A!=NULL&&B==NULL) return false;
        if(A==NULL&&B!=NULL) return false;
        return isSameTree(A,B)//root和subRoot相等
        ||isSubStructure(A->left,B)//subRoot是root的左子树的子树
        ||isSubStructure(A->right,B);//subRoot是root的右子树的子树
    }
};

五、自顶向下计算属性

222. 完全二叉树的节点个数（中等难度）

class Solution {
public:
    int countNodes(TreeNode* root) {
        //终止条件
        if(root==NULL)return 0;
        int leftCount=countNodes(root->left);
        int rightCount=countNodes(root->right);
        return 1+leftCount+rightCount;
    }
};

104. 二叉树的最大深度（简单难度）

剑指 Offer 55 - I. 二叉树的深度（简单难度）

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。其中根节点所在深度为1.

点评

思路一：递归思想

用一个外部变量在遍历二叉树时记录每个节点所在的深度，遇到叶节点就更新一次最大深度。

depth 记录当前递归到的节点深度，那么dfs()的前序位置就是刚进入当前节点时刻，depth+1，后序位置就是刚离开当前节点时刻，depth-1

class Solution {
public:
    int res=0;
    int maxDepth(TreeNode* root) {
        dfs(root,1);
        return res;
    }
    void dfs(TreeNode* root,int depth){
        if(root==nullptr) return;
        // （一）前序位置 depth++
        // 如果达到叶节点，则达到了最大深度
        if(root->left==nullptr&&root->right==nullptr) res=max(res,depth);
        // 搜索两个子树方向
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);
        // （二）后序位置 depth--
    }
};

思路二：分治思想

class Solution {
public:
    //定义递归函数，输入一个根节点，返回其最大深度
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        // 利用定义，计算左右子树的最大深度
        int leftD = maxDepth(root->left);
        int rightD = maxDepth(root->right); 
        // 整棵树的最大深度等于左右子树的最大深度取最大值，然后再加上根节点自己
        return max(leftD,rightD)+1;
    }
};

559. N 叉树的最大深度（简单难度）

思路一：递归思想

class Solution {
public:
    int res=0;
    int maxDepth(Node* root) {
       dfs(root, 1);
       return res;
    }
    void dfs(Node* root,int depth){
        if(root==nullptr) return;
        // 如果达到叶节点，则达到了最大深度
        if(root->children.size()==0) res=max(res, depth);
        for(Node* child:root->children){
            dfs(child,depth+1);
        }
    }
};

思路二：分治思想

class Solution {
public:
    //定义递归函数，输入一个根节点，返回其最大深度
    int maxDepth(Node* root) {
        if(root == NULL) return 0;
        int maxChild=0;
        for(Node* child:root->children){
            int x=maxDepth(child);// 利用定义，计算每个子树的最大深度
            maxChild=max(maxChild,x);// 保存所有子树中的最大深度
        }
        return maxChild+1;//整个树的最大深度=所有子树中的最大深度+1
    }
};

111. 二叉树的最小深度（简单难度）

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int leftD = minDepth(root->left);
        int rightD = minDepth(root->right);
        // 当只有左子树时，这时并不是最低点
        if(root->left!=NULL&&root->right==NULL)return 1+leftD;
        // 当只有右子树时，这时并不是最低点
        if(root->left==NULL&&root->right!=NULL)return 1+rightD;
        return min(leftD,rightD)+1;
    }
};

543. 二叉树的直径（简单难度）

问题：给定一棵二叉树，返回它的直径长度（一棵二叉树的直径长度是任意两个结点路径长度中的最大值，这条路径可能穿过也可能不穿过根结点）。

点评

二叉树的直径=左子树的最大深度+右子树的最大深度

由于求直径，需要先求出左右子树的最大深度，所以dfs()需要后序遍历。

class Solution {
public:
    /*二叉树的直径=左子树的最大深度+右子树的最大深度*/
    int maxDia=0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return maxDia;
    }
    // 输入一个根节点，返回其最大深度
    int dfs(TreeNode* root){
        if(root==nullptr) return 0;
        int leftDepth=dfs(root->left);
        int rightDepth=dfs(root->right);
        // 后序位置
        maxDia=max(maxDia,leftDepth+rightDepth);
        return 1+max(leftDepth,rightDepth);
    }
};

110. 平衡二叉树（简单难度）

剑指 Offer 55 - II. 平衡二叉树（简单难度）

class Solution {
public:
    //求某个节点的高度
    int getHeight(TreeNode* root) {
        if(root==NULL) return 0;
        int leftHeight=getHeight(root->left);
        int rightHeight=getHeight(root->right);
        return max(leftHeight,rightHeight)+1;
    }
    //判断是否是平衡二叉树
    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        //左子树不是平衡二叉树
        if(!isBalanced(root->left)) return false;
        //右子树不是平衡二叉树
        if(!isBalanced(root->right)) return false;
        //左右子树的高度绝对值是否小于1
        int leftHeight=getHeight(root->left);
        int rightHeight=getHeight(root->right);
        if(abs(leftHeight-rightHeight)<=1) return true;
        else return false;
    }
};

六、自顶向下回溯路径

257. 二叉树的所有路径（简单难度）

class Solution {
public:
    vector<string> res;
    void getPaths(TreeNode* node,string path){
        path+=to_string(node->val);//添加当前节点
        //如果是叶子节点,说明一条路径结束,递归返回
        if(node->left==nullptr&&node->right==nullptr){
            res.push_back(path);
            return;
        }
        //如果当前节点的左节点存在,递归左节点
        if(node->left) getPaths(node->left,path+"->");//递归添加该节点
        //如果当前节点的右节点存在,递归右节点
        if(node->right) getPaths(node->right,path+"->");//递归添加该节点
        
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        getPaths(root,"");
        return res;
    }
};

112. 路径总和（简单难度）

class Solution {
public:
    bool traversal(TreeNode* cur, int count) {
        // 如果是叶子节点，并且为0,返回真
        if (!cur->left && !cur->right && count == 0) return true; 
        // 如果是叶子节点，但是不为0，返回假
        if (!cur->left && !cur->right) return false; 
        // 如果左节点存在，递归处理左节点
        if (cur->left) { // 左
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        // 如果右节点存在，递归处理右节点
        if (cur->right) { // 右
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        return traversal(root, targetSum - root->val);
    }
};

113. 路径总和 II

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

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    // 递归函数不需要返回值，因为我们要遍历整个树
    void traversal(TreeNode* cur, int count) {
        // 如果是叶子节点，且为0,添加到结果中并返回
        if (!cur->left && !cur->right && count == 0) { 
            result.push_back(path);
            return;
        }
        // 如果是叶子节点，不为0,直接返回
        if (!cur->left && !cur->right) return ; 
        // 如果是左节点存在，递归左节点
        if (cur->left) { 
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traversal(cur->left, count);    // 递归
            count += cur->left->val;        // 回溯
            path.pop_back();                // 回溯
        }
        // 如果右节点存在，递归右节点
        if (cur->right) { // 右 （空节点不遍历）
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);   // 递归
            count += cur->right->val;       // 回溯
            path.pop_back();                // 回溯
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return result;
        path.push_back(root->val); // 把根节点放进路径
        traversal(root, targetSum - root->val);
        return result;
    }
};

437. 路径总和 III（中等难度）

方法一：递归法

class Solution {
public:
    // 查找包含root节点并且和为sum的路径个数
    int findPath(TreeNode* root,int sum){
        int result=0;
        if(root==nullptr) return result;
        // 如果加上root，和满足则结果+1
        if(sum==root->val) result+=1;
        // 查找包含root左节点
        result+=findPath(root->left,sum-root->val);
        // 查找包含root右节点
        result+=findPath(root->right,sum-root->val);
        return result;
    }
    // 查找包含root/不包含root并且和为targetSum的路径个数
    int pathSum(TreeNode* root, int targetSum) {
        int result=0;
        if(root==nullptr) return result;
        result+=findPath(root,targetSum);// 查找包含root节点并且和为sum的路径个数
        result+=pathSum(root->left,targetSum);// 查找包含root节点并且和为sum的路径个数
        result+=pathSum(root->right,targetSum);
        return result;
    }
};

方法二：前缀和+递归法

class Solution {
public:
    unordered_map<long long, int> dict;  //<[0,b]的前缀和，出现次数>
    int res = 0; 
    // pathSum：[a,root]的目标和;curSum：[0,root]的前缀和
    void dfs(TreeNode* root,int pathSum,int curSum){
        if (root == nullptr)    return;
        curSum += root->val; //当前节点的前缀和[0,b]
      	// [0,b]的前缀和-[a,b]的前缀和=[0,a-1]的前缀和，哈希表中是否存在
        if (dict.count(curSum - pathSum)){ 
          res += dict[curSum - pathSum];//
        }
        // 将[0,b]的前缀和存入哈希表，遍历是否存在满足要求的子树
        dict[curSum]++;
        dfs(root->left,pathSum, curSum);//查看是否存在root的左节点的
        dfs(root->right,pathSum, curSum); 
      	// 当子树结束时，应当把子树从哈希表中移除 (回溯：将一切复原，然后结束)。
        dict[curSum]--; 
    }
    // 查找包含root/不包含root并且和为targetSum的路径个数
    int pathSum(TreeNode* root, int targetSum) {
      	// 注意 前缀和中, [a, b] = [0, b] - [0, a-1] 。
        // 对于包含根节点的路径，是无法找到 a-1 的。所以需要一个虚拟根节点。
        dict[0] = 1;  
        dfs(root,targetSum, 0); //targetSum视为[a,b]区间的和
        return res; 
    }
};

404. 左叶子之和（简单难度）

class Solution {
public:
    int preOrder(TreeNode* root,bool isleft){
        int result=0;
        // 如果是空节点，返回0
        if(root==NULL) return 0;
        // 如果是左叶子，返回其值
        if(isleft&&root->left==NULL&&root->right==NULL) return root->val;
        result+=preOrder(root->left,true);// 递归左节点
        result+=preOrder(root->right,false);// 递归右节点
        return result;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        return preOrder(root,false);
    }
};

七、自底向上寻找祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先（简单难度）

236. 二叉树的最近公共祖先（中等难度）

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //如果当前节点为空，直接返回空
        if(root==NULL) return NULL;
        //如果当前节点值和p或者q中的一个相等，则返回当前节点
        if(p->val==root->val||q->val==root->val)return root;
        //递归调用
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        //如果左子树和右子树分别存在p和q
        if (left != NULL && right != NULL)return root;
        //如果右子树存在p和q
        if (left == NULL && right != NULL)return right;
        //如果左子树存在p和q
        if (left != NULL && right == NULL) return left;
        return NULL;
    }
};

968. 监控二叉树（困难难度）

class Solution {
public:
    /* 摄像头不可以放在叶节点上,因为摄像头可以覆盖上中下三层
    如果把摄像头放在叶节点上，就浪费的一层的覆盖，不是最少摄像头数
    对于每个节点都存在三个状态：无覆盖、有摄像头、已覆盖
    每个节点的当前状态由其2个子节点的状态决定（从底向上遍历二叉树）：
    1、左右节点都有覆盖,当前节点相当于叶节点，不能有摄像头，是无覆盖
    2、有一个子节点是没覆盖,当前节点应该有摄像头
    3、有一个子节点是摄像头,该节点是已覆盖*/
    int res;
    // 定义：遍历cur为根的树，返回cur的状态
    // 0：该节点无覆盖 1：该节点有摄像头 2：该节点已覆盖
    int dfs(TreeNode* cur) {
        // 空节点，可以看做该节点是已覆盖
        if (cur==NULL) return 2;
        int left = dfs(cur->left);    // 左
        int right = dfs(cur->right);  // 右
        // 情况1：左右节点都有覆盖,当前节点相当于叶节点，不能有摄像头，是无覆盖
        if (left == 2 && right == 2) return 0;
        // 情况2：有一个子节点没覆盖,当前节点应该有摄像头
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            res++;
            return 1;
        }
        // 情况3：有一个子节点是摄像头,该节点是已覆盖
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        if (left == 1 || right == 1) return 2;
        return -1;// 这个return -1 不会走到
    }
    int minCameraCover(TreeNode* root) {
        res = 0;
        // 情况4
        if(dfs(root) == 0)  res++;
        return res;
    }
};