leetcode二叉树遍历题目

二叉树遍历的非递归实现

1.二叉树的层次遍历

题目描述

代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>>a;
        if(root==NULL)
        {
            return a;
        }
        TreeNode* p=NULL;
        //定义一个队列，存储二叉树结点的地址
        queue<TreeNode*>nodes;
        //根节点入队
        nodes.push(root);
        while(!nodes.empty())
        {
            //队列中有几个元素
            int size=nodes.size();
            vector<int>b;
            //size为多大，代表二叉树这一行一共多少个元素，需要push_back多少次
            while(size--)
            {
            p=nodes.front();
            b.push_back(p->val);
            nodes.pop();
            //如果左孩子不为空，将左孩子入队列
            if(p->left!=NULL)
            {
                nodes.push(p->left);
                
            }    
            //如果右孩子不为空，将右孩子入队列
            if(p->right!=NULL)
            {
                nodes.push(p->right);
  
            }
            }
            a.push_back(b);
        }
        return a;
    }
};

2. 二叉树的前序遍历

题目描述

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* T=root;
        vector<int>a;
        stack<TreeNode*>nodes;
        //判断条件1.如果栈为空，无法出栈；2.如果指向为空，就无法压栈。只要两个条件满足一个就可以进行下面的操作
        while(T!=NULL||!nodes.empty())
        {
            while(T)
            {
                a.push_back(T->val);
                //压栈这个函数(向栈顶添加元素)是没有返回值的,void push ( const T& x );
                nodes.push(T);
                T=T->left;
            }
            //返回值为bool型的函数，栈非空；bool empty ( ) const;
            if(!nodes.empty())
            {
                //top函数是有返回值的
                T=nodes.top()->right;
                nodes.pop();                
            }               
        }
        return a;
    }
};

3.二叉树的中序遍历

题目描述

中序遍历和前序遍历就把其中一行换一下位置
代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* T=root;
        stack<TreeNode*>nodes;
        vector<int>a;
        while(T!=NULL||!nodes.empty())
        {
            while(T)
            {
                nodes.push(T);
                T=T->left;
            }
            if(!nodes.empty())
            {
                a.push_back(nodes.top()->val);
                T=nodes.top()->right;
                nodes.pop();
            }
        }
        return a;
    }
};

3.二叉树的后序遍历

题目描述

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*>nodes;
        vector<int>a;
        TreeNode *T=root;
        TreeNode *P=NULL;
        while(T!=NULL||!nodes.empty())
        {
            while(T)
            {
             nodes.push(T);
              T=T->left;
            }
            if(!nodes.empty())
            {
                //如果没有右孩子结点，或者右孩子已经访问过
                if(nodes.top()->right==NULL||nodes.top()->right==P)
                {
                    a.push_back(nodes.top()->val);
                    P=nodes.top();
                    nodes.pop();
                }
                //如果有右孩子结点，就不能访问这个结点，需要继续遍历它的右子树
                else
                {
                    T=nodes.top()->right;
                }
            }
        }
        return a;
    }
};