一、二叉树的遍历

1.1 二叉树的层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
    if(root == nullptr) return {};	//判断根节点是否为空
    queue<TreeNode*> que;	//创建队列
    que.push(root);	//根节点入队
    vector<int> ret;	
    while(!que.empty()){
        auto tmp = que.front();	//记录队列中的第一个节点
        que.pop();	//出队
        ret.push_back(tmp->val);//将该节点的值记录下来
        if(tmp->left)    que.push(tmp->left);	//队列是先进先出，因此先将左节点入队
        if(tmp->right)    que.push(tmp->right);	//右节点入队
    }
    return ret;
}

1.2 前序，中序，后序遍历（递归）

void dfs(TreeNode* root, vector<int>& res){
    if(root==nullptr)   return;
    //res.push_back(root->val);	//前序遍历
    dfs(root->left, res);
    //res.push_back(root->val);	//中序遍历
    dfs(root->right, res);
    //res.push_back(root->val);	//后序遍历
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    dfs(root, res);
    return res;
}

1.3 前序，中序，后序遍历（迭代）

//前序遍历
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if(root == nullptr) return {};
    stack<TreeNode*>stk;
    stk.push(root);
    while(!stk.empty()){
        TreeNode* tmp = stk.top();
        stk.pop();
        res.push_back(tmp->val);
        if(tmp->right)  stk.push(tmp->right);
        if(tmp->left)   stk.push(tmp->left);
    }
    return res;
}

//中序遍历，三个循环
vector<int> inorderTraversal(TreeNode* root) {
    vector<int>res;
    if(root == nullptr) return res;
    stack<TreeNode*> stk;
    stk.push(root);	//根节点入栈
    while(!stk.empty()){
        //到达了二叉树的左下角
        while(stk.top()->left != nullptr)   stk.push(stk.top()->left);
        
        while(!stk.empty()){
            TreeNode* tmp = stk.top();	stk.pop();	//遍历左下角的节点
            res.push_back(tmp->val);
            if(tmp->right){	//判断该节点是否存在右子树，若存在，将右子树节点入栈，重新找到该右子树的左下角继续重复上述过程
                stk.push(tmp->right);
                break;
            }
        }    
    }
    return res;
}

//后序遍历，需要记录上一次出栈的节点
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if(root == nullptr) return res;
    stack<TreeNode*> stk;
    stk.push(root);
    TreeNode* lastnode = nullptr;
    while(!stk.empty()){
        //找到左下角的节点
        while(stk.top()->left != nullptr)   stk.push(stk.top()->left);
        while(!stk.empty()){
            //判断上一次出栈节点是否当前节点的右节点，或者当前节点的右节点是否为空，满足任一条件，将当前节点输出，
            if(lastnode == stk.top()->right || stk.top()->right == nullptr){
                TreeNode* node = stk.top(); stk.pop();
                res.push_back(node->val);
                lastnode = node;
            }
            //查找该节点是否存在右子树
            else if(stk.top()->right != nullptr){
                stk.push(stk.top()->right);
                break;
            }
        }
    }
    return res;
}

二、二叉树的其他题目

LeetCode 105: 从前序遍历与中序遍历序列构造二叉树
输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]
题目分析：
    前序遍历中第一个节点就是根节点，第二个节点就是左子树的根节点......
    中序遍历中根节点左边就是左子树
因此，我们通过前序遍历来找到节点，通过在中序遍历中的位置来判断是左子树还是右子树根节点，如下图所示：

class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

LeetCode 105: 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
题目分析：
    每个节点不仅有它的 val 值，同时还有一些二叉树的深度，节点数值的和等隐含的属性。在求路径和时，当节点遍历时，将节点与路径和一起作为递归的参数，通过深度优先策略可以判断是否有等于targetSum的路径和。
//递归法
bool hasPathSum(TreeNode* root, int targetSum) { 
    if (root == nullptr) {
        return false;
    }
    if(!root->left && !root->right){
        if(root->val == targetSum)  return true;
        else
            return false;
    }
    bool f1 = hasPathSum(root->left, targetSum - root->val);	//沿着左子树去找
    bool f2 = hasPathSum(root->right, targetSum - root->val);	//沿着右子树去找
    return f1 || f2;
}
//迭代法
 bool hasPathSum(TreeNode* root, int targetSum) {
     if(root == nullptr) return false;
     stack<pair<TreeNode*, int>> stk;	//将下一个节点与剩余的路径和同时存放到栈内
     stk.push(pair<TreeNode*, int>(root, root->val));
     while(!stk.empty()){
         pair<TreeNode*, int> cur = stk.top();   stk.pop();	//取出栈顶的元素，first 为节点，second 为该节点的 val
         TreeNode* node = cur.first;
         int path_value = cur.second;

         if(node->left == nullptr && node->right == nullptr && path_value==targetSum){
             return true;
         }
		// 深度优先搜索，其实就是二叉树的前序遍历，将路径上的节点和剩余路径和一并存入，如果存在
         // node->left == nullptr && node->right == nullptr && path_value==targetSum, 那么返回 true
         if(node->right != nullptr)
             stk.push(pair<TreeNode*, int>(node->right, path_value+node->right->val));
         if(node->left != nullptr)
             stk.push(pair<TreeNode*, int>(node->left, path_value+node->left->val));
     }
     return false;
    }

LeetCode 113: 路径总和II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
题目分析：
    这道题跟上题差不多，只不过需要额外定义两个数组，res 和 path。其中 path 记录 dfs 遍历到的节点，当满足条件时就把 path 存入 res, 代替 “return true” 这一步。如果不满足条件，在 dfs 结束时记得弹出 path 的顶端 val， 回退到上一个节点。
//递归法
void dfs(TreeNode* root, int targetSum, vector<vector<int>>& res, vector<int>& path){
    if (root == nullptr) 
        return;
    path.push_back(root->val);
    if(!root->left && !root->right && root->val==targetSum){
        res.push_back(path);
    }
    if(root->left)  dfs(root->left, targetSum - root->val, res, path);
    if(root->right)  dfs(root->right, targetSum - root->val, res, path);
    path.pop_back(); //回溯，返回到上一个节点，撤销处理结果
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> res;
    vector<int> path;
    dfs(root, targetSum, res, path);
    return res;
}

LeetCode 199: 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
题目分析：
    这道题采用广度优先的策略会比较好理解，可以参考 `LeetCode 107: 二叉树的层序遍历II`，在层序遍历中，每一个层的最后一个节点就是所要找到的值。如果采用深度优先算法来理解，首先从根节点先访问右子树来确保右边的节点首先出现，然后使用一个 depth 变量来判断该节点是否被挡住。
vector<int> rightSideView(TreeNode* root) {
    //广度优先策略
    if(root == nullptr) return {};
    queue<TreeNode*> que;	//定义层序遍历的队列
    vector<int> res;
    que.push(root);
    while(!que.empty()){
        int cur_size = que.size();	//记录该层的节点个数
        TreeNode* node = nullptr;
        //随着遍历，不断将下一层的节点入队，当遍历完该层的节点时，node所代表的就是该层的最右边节点
        for(int i=0; i<cur_size; i++){	
            node = que.front(); que.pop();
            if(node->left)  que.push(node->left);
            if(node->right)  que.push(node->right);
        }
        res.push_back(node->val);
    }     
    return res;
}   
//深度优先策略
void dfs(TreeNode* root, int depth, vector<int>& res){
    if(root == nullptr) return;
    if(depth == res.size()){	//通过判断 depth 是否与 res 的长度相等，来判断该节点是否被挡住
        res.push_back(root->val);
    }
    dfs(root->right, depth+1, res);
    dfs(root->left, depth+1, res);
}
vector<int> rightSideView(TreeNode* root) {
    //深度优先策略
    vector<int> res;
    dfs(root, 0, res);	//假设根节点的深度为 0
    return res;
}

LeetCode 113: 二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
输入：root = [3,9,20,null,null,15,7]
输出：2
题目分析：
    本题同样可以采取 DFS 和 BFS 的策略。
    使用 BFS 进行层序遍历，当碰到第一个节点 node 且 node->left 与 node->right 均为 nullptr 时，该节点的深度就是二叉树的最小深度。
    使用 DFS 进行前序遍历，必须要记录每一条路径的深度，然后最小的那个就是结果。
//广度优先策略
int minDepth(TreeNode* root) {
    int res=0;
    if(root == nullptr) return res;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()){
        int cur_size = que.size();	//记录下该层的节点个数
        res++;	//没经过一层，深度加 1
        for(int i=0; i<cur_size; i++){
            TreeNode* node = que.front(); que.pop();
            //如果该层中有某个节点的左右子节点都为空，那么提前返回结果
            if(node->left == nullptr && node->right == nullptr)
                return res;    
            if(node->left)  que.push(node->left);
            if(node->right) que.push(node->right);
        }
    }
    return res;    
}
//深度优先策略
int minDepth(TreeNode *root) {
    if (root == nullptr) {
        return 0;
    }

    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }

    int min_depth = INT_MAX;
    if (root->left != nullptr) {
        min_depth = min(minDepth(root->left), min_depth);
    }
    if (root->right != nullptr) {
        min_depth = min(minDepth(root->right), min_depth);
    }

    return min_depth + 1;
}

部分二叉树题目汇总