LeetCode刷题——二叉树1

二叉树定义

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}
	TreeNode(int x,TreeNode* left,TreeNode* right):val(x),left(left),right(left){}
};
1
2
3
4
5
6
7

二叉树遍历

前序遍历（根左右）

递归

class Solution {
public:
    void traverse(TreeNode* t,vector<int>& ans){
        if(t==nullptr) return;
        ans.push_back(t->val);
        traverse(t->left,ans);
        traverse(t->right,ans);
    } 
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root,ans);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代

class Solution {
public: 
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*>s;
        if(root==nullptr) return ans;
        s.push(root);
        while(!s.empty()){
            TreeNode* p=s.top();
            ans.push_back(p->val);
            s.pop();
            if(p->right!=nullptr) s.push(p->right);
            if(p->left!=nullptr) s.push(p->left);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

中序遍历（左根右）

递归

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (root==nullptr) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

后序遍历（左右根）

递归

class Solution {
public:
    void traverse(TreeNode* t,vector<int>& ans){
        if(t==nullptr) return;
        
        traverse(t->left,ans);
        traverse(t->right,ans);
        ans.push_back(t->val);
    } 
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root,ans);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15