二叉树的遍历
递归遍历思路解析
二叉树的前中后序遍历，其实就是递归的简单应用二叉树遍历算法 java二叉树遍历算法 java 二叉树遍历系列，写递归我一般先写递归出口和边界，这样能更容易理清思路。
学过数据结构的朋友二叉树遍历算法 java，二叉树递归遍历的原理应该不用再介绍了。下面就看代码吧。
手撕代码
//前序遍历
class Solution {
private:
vector res;
public:
vector& preorderTraversal(TreeNode* root) {
//方法的返回值是成员变量的引用，若使用局部变量，请使用值传递的方式。
helper(root, res);
return res;
}
void helper(TreeNode* root, vector& res) {
if (root != nullptr) {
res.push_back(root->val);
if (root->left != nullptr) {
helper(root->left, res);
}
if (root->right != nullptr) {
helper(root->right, res);
}
}
}
};
//[中序遍历][5]
class Solution {
private:
vector res;
public:
vector& inorderTraversal(TreeNode* root) {
helper(root, res);
return res;
}
void helper(TreeNode* root, vector& res) {
if (root != nullptr) {
if (root->left != nullptr) {
helper(root->left, res);
}
res.push_back(root->val);
if (root->right != nullptr) {
helper(root->right, res);
}
}
}
};
//后序遍历
class Solution {
private:
vector res;
public:
vector& postorderTraversal(TreeNode* root) {
helper(root, res);
return res;
}
void helper(TreeNode* root, vector& res) {
if (root != nullptr) {
if (root->left != nullptr) {
helper(root->left, res);
}
if (root->right != nullptr) {
helper(root->right, res);
}
res.push_back(root->val);
}
}
};
迭代遍历
二叉树的迭代遍历就是不再使用系统栈，用循环代替递归
前序遍历
//前序遍历
//第一种解法
//改解法在栈中保存了二叉树的左右子树，更符合人工遍历二叉树时的思维
class Solution {
private:
vector res;
public:
vector& preorderTraversal(TreeNode* root) {
stack stack;
if (root == nullptr)
return res;
TreeNode* ptr = root;
while (ptr || !stack.empty()) {
if(ptr){
res.push_back(ptr->val);
stack.push(ptr);
ptr = ptr->left;
}
else
{
ptr = stack.top();
ptr = ptr->right;
//这里记得一定要pop,因为前序遍历中，访问了该节点的右子树后，该节点就再也不用被访问了。
stack.pop();
}
}
return res;
}
};
//第二种解法
//该解法是前一种在形式上的简化版，只需要在栈中保存右子树即可。
class Solution {
private:
vector res;
public:
vector& preorderTraversal(TreeNode* root) {
stack stack;
if (root == nullptr)
return res;
TreeNode* ptr = root;
while (ptr || !stack.empty()) {
if (ptr) {
res.push_back(ptr->val);
if (ptr->right) {
stack.push(ptr->right);
}
ptr = ptr->left;
}
else
{
ptr = stack.top();
stack.pop();
}
}
return res;
}
};
//这种解法其实也是利用了前序遍历先遍历根，再遍历左子树，最后右子树的特性，结合栈先进后出的特性去实现。
class Solution {
private:
vector res;
public:
vector& preorderTraversal(TreeNode* root) {
stack stack;
if (root == nullptr)
return res;
stack.push(root);
TreeNode* ptr = nullptr;
while (!stack.empty())
{
ptr = stack.top();
stack.pop();
res.push_back(ptr->val);
if (ptr->right)
stack.push(ptr->right);
if (ptr->left)
stack.push(ptr->left);
}
return res;
}
};
中序遍历
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
vector res;
stack st;
TreeNode* ptr = root;
while (ptr || !st.empty()) {
if (ptr) {
st.push(ptr);
ptr = ptr->left;
}
else {
ptr = st.top();
st.pop();
res.push_back(ptr->val);
ptr = ptr->right;
}
}
return res;
}
};
后序遍历
//这种做法丢失了后序遍历从前到后的顺序
class Solution {
public:
vector postorderTraversal(TreeNode *root) {
stack nodeStack;
vector result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->left)
nodeStack.push(node->left);
if(node->right)
nodeStack.push(node->right);
}
reverse(result.begin(),result.end());
return result;
}
};
//更欣赏这种写法
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
vector res;
if (root == nullptr){
return res;
}
TreeNode* ptr = root;
TreeNode* last = nullptr;
stack st;
while(ptr || !st.empty()){
if (ptr){
st.push(ptr);
ptr = ptr->left;
}
else{
TreeNode* node = st.top();
if(node->right && last!= node->right){
ptr = node->right;
}
else{
res.push_back(node->val);
last = node;
st.pop();
}
}
}
return res;
}
};