Leetcode60天刷题Day14-二叉树的递归遍历和迭代遍历

二叉树的递归遍历

题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

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

题目：给你二叉树的根节点 root ，返回它节点值的 中序 遍历。

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

题目：给你二叉树的根节点 root ，返回它节点值的 后序 遍历。

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

二叉树的迭代遍历

题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

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

题目：给你二叉树的根节点 root ，返回它节点值的 中序 遍历。

class Solution{
public:
	vector<int> inorderTraversal(TreeNode* root){
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL) return result;
		TreeNode* cur = root;
		while(cur || !st.empty()){
			if(cur != NULL) {
				st.push(cur);
				cur = cur->left;
			}
			if(cur == NULL){
				cur = st.top();
				st.pop();
				result.push_back(cur->val);
				cur = cur->right;
			}
		}
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目：给你二叉树的根节点 root ，返回它节点值的 后序 遍历。

class Solution{
public:
	vector<int> preorderTraversal(TreeNode* root){
		stack<TreeNode*> st;
		vector<int> result;
		if(root == NULL) return result;
		st.push(root); 
		while(!st.empty()){
			TreeNode* temp = st.top();
			st.pop();
			result.push_back(temp->val);
			if(temp->left) st.push(temp->left);
			if(temp->right) st.push(temp->right);
		}
		reverse(result.begin(), result.end()); 
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18