遍历二叉树

深度优先遍历（栈）

保证入栈节点不是空节点！

前序遍历（中左右）

递归

void visit(TreeNode* cur, vector<int>& res){
	if(cur == nullptr) return;
	res.push_back(cur->val); //中
	visit(cur->left, res);   //左
	visit(cur->right, res);  //右
}
vector<int> preorderTraversal(TreeNode* root){
	vector<int> result;
	visit(root, result);
	return result;
}

迭代

vector<int> preorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	vector<int> res;
    TreeNode* cur = root;
	while(cur != nullptr || !st.empty()){
		if(cur != nullptr){
			res.push_back(cur->val);//**********该行变化**************
			st.push(cur);
			cur = cur->left;
		}else{
			cur = st.top();
			st.pop();
			cur = cur->right;
		}
	}
    return res;
}

中序遍历（左中右）

递归

void visit(TreeNode* cur, vector<int>& res){
	if(cur == nullptr) return;
    visit(cur->left, res);   //左
    res.push_back(cur->val); //中
	visit(cur->right, res);  //右
}
vector<int> inorderTraversal(TreeNode* root){
	vector<int> result;
	visit(root, result);
	return result;
}

迭代

vector<int> inorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	vector<int> res;
    TreeNode* cur = root;
	while(cur != nullptr || !st.empty()){
		if(cur != nullptr){  // 指针来访问节点，访问到最底层
			st.push(cur);    // 将访问的节点放进栈
			cur = cur->left; 
		}else{
			cur = st.top();
			st.pop(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
            res.push_back(cur->val); //**********该行变化**************
			cur = cur->right;        
		}
	}
    return res;
}

后序遍历（左右中）

递归

void visit(TreeNode* cur, vector<int>& res){
	if(cur == nullptr) return;
	visit(cur->left, res);   //左
	visit(cur->right, res);  //右
    res.push_back(cur->val); //中
}
vector<int> postorderTraversal(TreeNode* root){
	vector<int> result;
	visit(root, result);
	return result;
}

迭代

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode*> st;
	TreeNode* cur = root;
	TreeNode* prenode;
	while(cur != nullptr || !st.empty()){
		if(cur != nullptr){
			st.push(cur);
			cur = cur->left;
		}else{
			cur = st.top();
			st.pop();
			if(cur->right == nullptr || cur->right == prenode){//没有右结点或已经访问过
				res.push_back(cur->val);
				prenode = cur;
				cur = nullptr;
			}else{
				st.push(cur);
				cur = cur->right;
			}
		}
	}
	return res;
}

// 或反转变化的前序（根右左）遍历
vector<int> REVERpreorderTraversal(TreeNode* root) {
	stack<TreeNode*> st;
	vector<int> res;
    TreeNode* cur = root;
	while(cur != nullptr || !st.empty()){
		if(cur != nullptr){
			res.push_back(cur->val);
			st.push(cur);
			cur = cur->right;//**********该行变化**************
		}else{
			cur = st.top();
			st.pop();
			cur = cur->left;//**********该行变化**************
		}
	}
    reverse(res.begin(), res.end());
    return res;
}

// 或双栈解法
class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        if (!root) return res;
        std::stack<TreeNode*> st1;
        std::stack<TreeNode*> st2;
        st1.push(root);
        // 栈⼀顺序存储
        while (!st1.empty()) {
            TreeNode* node = st1.top();
            st1.pop();
            st2.push(node);
            if (node->left) st1.push(node->left);
            if (node->right) st1.push(node->right);
        }
        // 栈⼆直接输出
        while (!st2.empty()) {
            res.push_back(st2.top()->val);
            st2.pop();
        }
        return res;
    }
};

广度优先遍历（队列）

层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root != nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> res;
            for(int i = 0; i < size; ++i){
                TreeNode* node = que.front();
                res.push_back(node->val);
                if(node->left != nullptr) que.push(node->left);
                if(node->right != nullptr) que.push(node->right);
                que.pop();
            }
            result.push_back(res);
        }
        return result;
    }
};

二叉搜索树（BST）

不需要使用栈或队列~

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};