二叉树的遍历 递归+迭代

递归法

前序遍历

/** * Definition for a binary tree node. * 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:
    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> postorderTraversal(TreeNode* root) {
    
        vector<int>result;
        traversal(root,result);
        return result;
    }
};

中序遍历和后序遍历的实现也很简单，只要把前序遍历中的顺序调换一下即可。

迭代法

递归中是隐藏了一个栈，在迭代法中需要将栈显式的表现出来。

前序遍历

/** * Definition for a binary tree node. * 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> preorderTraversal(TreeNode* root) {
    
        vector<int> result;
        stack<TreeNode*> st;
        st.push(root);

        while(!st.empty())
        {
    
            TreeNode* cur=st.top();//访问栈顶元素
            st.pop();//弹出栈顶元素
            if(cur!=NULL) //当栈顶元素不为空时(没访问到叶子结点时)
                result.push_back(cur->val);
            else //若栈顶元素为空(遇到叶子结点)
                continue;

            st.push(cur->right);//右子树结点先入栈
            st.push(cur->left);
        }
        return result;
    }
};

后序遍历

后序遍历只要在前序遍历的基础上稍做改动就好。
前序遍历是：根、左、右，最终的后序遍历是：左、右、根。
思路：在前序遍历中，改变为根、右、左，然后在反转一下vector中的顺序即可。

中序遍历

中序遍历就和其它两种不一样了，入栈顺序不一致，先上代码

/** * Definition for a binary tree node. * 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> preorderTraversal(TreeNode* root) {
    
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        
        while(cur!=NULL || !st.empty())
        {
    
            if(cur!=NULL)
            {
    
                st.push(cur);
                cur=cur->left;
            }
            else
            {
    
                cur=st.top();
                st.pop();
                result.push_back(cur->val);
                cur=cur->right;
            }
        }
        return result;
    }
};

访问当前结点，如果不为空，就访问其左结点，如果为空但此时栈不为空，就访问栈顶元素，然后访问其右结点。