结构体定义

Leetcode中TreeNode结构体定义如下：

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

二叉树的前序遍历

递归版本：

class Solution {
public:

    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) 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;
        stack<TreeNode*> stack;
        if(root){
            stack.push(root);
        }
        while(!stack.empty()){
            TreeNode* curr = stack.top();
            stack.pop();
            res.push_back(curr->val);
            if(curr->right != nullptr){
                stack.push(curr->right);
            }
            if(curr->left != nullptr){
                stack.push(curr->left);
            }
        }
        return res;
    }
};

二叉树的中序遍历

递归版本：

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

迭代版本：

class Solution {
public:
    vector<int> res;
    stack<TreeNode*> stack;
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* curr = root;
        while(!stack.empty() || curr != NULL){
            //找到最左侧节点
            while(curr != NULL){
                stack.push(curr);
                curr = curr->left;
            }
            //此时栈顶为最左节点，curr为最左节点的左孩子节点
            TreeNode* top = stack.top();
            stack.pop();
            res.push_back(top->val);
            //判断top节点是否存在右子树
            if(top->right != NULL)
                curr = top->right;
        }
        return res;
    }
};

二叉树后序遍历

递归版本：

class Solution {
public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        // 为空则直接返回
        if(root == NULL)
            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> ans;
        stack<TreeNode*> stk;
        if(root != NULL)
            stk.push(root);
        // curr存储当前退出栈的结点
        TreeNode* curr = root;
        while(!stk.empty())
        {
            TreeNode* top = stk.top();
            if(top->left != NULL && top->left != curr && top->right != curr)
                stk.push(top->left);
            else if(top->right != NULL && top->right != curr)
                stk.push(top->right);
            // 当左右子树都处理过或者不存在情况下，说明此结点可以弹栈
            else
            {
                ans.push_back(top->val);
                stk.pop();
                curr = top;
            }
        }
        return ans;
    }

};

相同的树

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};