https://leetcode.cn/problems/binary-tree-preorder-traversal/
二叉树的前序遍历

// 非递归实现
// class Solution {
// public:
//     vector<int> preorderTraversal(TreeNode* root) {
//         vector<int> ret;
//         if(root == nullptr) return ret;

//         stack<TreeNode*> st;
//         st.push(root);
//         while(!st.empty())
//         {
//             TreeNode* temp = st.top();
//             st.pop();
//             ret.push_back(temp->val);
//             if(temp->right) st.push(temp->right);
//             if(temp->left) st.push(temp->left);
//         }

//         return ret;
//     }
// };

// 递归实现
class Solution {
public:
    vector<int> ret;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return ret;
        
        ret.push_back(root->val);

        preorderTraversal(root->left);
        preorderTraversal(root->right);

        return ret;
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/binary-tree-inorder-traversal/
二叉树的中序遍历

// 非递归
// class Solution {
// public:
//     vector<int> inorderTraversal(TreeNode* root) {
//         vector<int> ret;
//         TreeNode* cur = root;
//         stack<TreeNode*> st;
//         while(cur != nullptr || !st.empty())
//         {
//             if(cur != nullptr)
//             {
//                 st.push(cur);
//                 cur = cur->left;
//             }
//             else if(cur == nullptr)
//             {
//                 cur = st.top();
//                 st.pop();
//                 ret.push_back(cur->val); // 中
//                 cur = cur->right;
//             }
//         }

//         return ret;
//     }
// };

// 递归
class Solution {
public:
    vector<int> ret;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == nullptr)
            return ret;
        inorderTraversal(root->left);
        ret.push_back(root->val);
        inorderTraversal(root->right);
        return ret;
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/binary-tree-postorder-traversal/
二叉树的后续遍历

// 非递归
// 思路：调整前序顺序，然后反转
// 前序（中左右）
// 调整（中右左）根据栈的特性，调整之后的顺序为中右左，入栈顺序为中左右
// 反转（左右中）      
// class Solution {
// public:
//     vector<int> postorderTraversal(TreeNode* root) {
//         vector<int> ret;
//         if(root == nullptr)
//             return ret;
//         stack<TreeNode*> st;
//         st.push(root);
//         while(!st.empty())
//         {
//             TreeNode* tmp = st.top();
//             st.pop(); 
//             ret.push_back(tmp->val);
//             if(tmp->left) st.push(tmp->left);
//             if(tmp->right) st.push(tmp->right);
//         }
//         reverse(ret.begin(), ret.end());
//         return ret;
//     }
// };
// 递归
class Solution {
public:
    vector<int> ret;
    void dfs(TreeNode* root)
    {
        if(root == nullptr)
            return;
        dfs(root->left);
        dfs(root->right);
        ret.push_back(root->val);
    
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return ret;
    }
};
https://leetcode.cn/problems/binary-tree-level-order-traversal/
二叉树的层序遍历

// 思路：借助队列，上一层带下一层
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;

        if(root == nullptr)
            return ret;

        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty())
        {
            vector<int> t;
            int oldsize = que.size();
            while(oldsize--)
            {
                TreeNode* tmp = que.front();
                que.pop();//取出上一层
                t.push_back(tmp->val);

                if(tmp->left)
                    que.push(tmp->left);
                if(tmp->right)
                    que.push(tmp->right);//带入下一层
            }

            ret.push_back(t);
        }

        return ret;
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/invert-binary-tree/
翻转二叉树

// 前序
// class Solution {
// public:
//     void dfs(TreeNode* root)
//     {
//         if(root == nullptr)
//             return;
        
//         // 交换左右孩子
//         TreeNode* tmp = root->left;
//         root->left = root->right;
//         root->right = tmp;

//         dfs(root->left);
//         dfs(root->right);
//     }

//     TreeNode* invertTree(TreeNode* root) {
//         dfs(root);    
//         return root;
//     }
// };

// 后序
// class Solution {
// public:
//     void dfs(TreeNode* root)
//     {
//         if(root == nullptr)
//             return;

//         dfs(root->left);
//         dfs(root->right);

//         // 交换左右孩子
//         TreeNode* tmp = root->left;
//         root->left = root->right;
//         root->right = tmp;
//     }

//     TreeNode* invertTree(TreeNode* root) {
//         dfs(root);    
//         return root;
//     }
// };

// 前序迭代
// class Solution {
// public:
//     TreeNode* invertTree(TreeNode* root) {
//         if(root == nullptr)
//             return nullptr;

//         stack<TreeNode*> st;
//         st.push(root);

//         while(!st.empty())
//         {
//             // 取出根节点
//             TreeNode* tmp = st.top();
//             st.pop();

//             // 交换左右孩子
//             TreeNode* t = tmp->left;
//             tmp->left = tmp->right;
//             tmp->right = t;

//             // 左右孩子入栈顺序与出栈顺序相反
//             if(tmp->right)
//                 st.push(tmp->right);
//             if(tmp->left)
//                 st.push(tmp->left);
//         }

//         return root;
//     }
// };

// 层序遍历
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)
            return nullptr;

        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty())
        {
            int oldsize = que.size();
            while(oldsize--)
            {
                TreeNode* tmp = que.front();
                que.pop();

                // 交换左右孩子
                TreeNode* t = tmp->left;
                tmp->left = tmp->right;
                tmp->right = t;

                // 带入下一层
                if(tmp->left)
                    que.push(tmp->left);
                if(tmp->right)
                    que.push(tmp->right);
            }
        }

        return root;
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/symmetric-tree/
对称二叉树

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right)
    {
        if(left == nullptr && right != nullptr)
            return false;
        else if(left != nullptr && right == nullptr)
            return false;
        else if(left == nullptr && right == nullptr)
            return true;
        //走到这里，说明左右都不为空
        if(left->val != right->val)
            return false;

        bool in = compare(left->right,right->left);
        bool out = compare(left->left,right->right);
        
        return in && out; 
    }

    bool isSymmetric(TreeNode* root) {
        if(root == nullptr)
            return true;

        return compare(root->left, root->right);
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
二叉树的最大深度
// 递归法
// 思路：后续遍历，height = max(left_height,right_height)+1
// class Solution {
// public:
//     int maxDepth(TreeNode* root) {
//         if(root == nullptr)
//             return 0; 
//         int left_height = maxDepth(root->left);
//         int right_height = maxDepth(root->right);

//         return max(left_height,right_height)+1;
//     }
// };

// 迭代法(层序遍历)
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr)
            return 0;

        int count = 0;
        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty())
        {
            count++; // 记录高度
            int oldsize = que.size();
            while(oldsize--)
            {
                TreeNode* tmp = que.front();
                que.pop();

                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
            }
        }

        return count;
    }
};
----------------------------------------------------------------------------------
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
二叉树的最小深度

// 注意：左右孩子都为空才说明遍历到最低点了
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr)
            return 0;

        int left_height = minDepth(root->left);
        int right_height = minDepth(root->right);

        if(root->left == nullptr && root->right != nullptr)
            return right_height+1;
        if(root->right == nullptr && root->left != nullptr)
            return left_height+1;

        return 1+min(left_height,right_height);
    }
};