二叉树的遍历

①中序遍历和前序遍历
前序和中序遍历的代码基本上一样,区别就在于什么时候把节点的val装入数组。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 #include <stack>
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        TreeNode *node=root;
        stack<TreeNode *> treeStack;
        vector<int> treeNum;
        int i=0;
        while(node!=NULL||!treeStack.empty())
        {
            if(node!=NULL)
            {
                treeStack.push(node);
                //treeNum.push_back(node->val);
                // 前序在这里添加进数组
                node=node->left;
            }
            else
            {
                node=treeStack.top();
                treeStack.pop();
                treeNum.push_back(node->val); //中序遍历是在这里添加入数组
                node=node->right;
            }
            i++;
        }
        return treeNum;
    }
};

③后序遍历
后序遍历就比前两个复杂多了,我自己做的时候百思不得其解要在什么时候退栈比较好。

思路是通过给每个节点设置isVisited属性来判断节点的children访问情况,isVisited=1代表访问过左子节点未访问右子节点,则接下来就要去访问右子节点。=2访问了全部子节点,就可以将数装入数组顺便抛出栈了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 #include<stack>
 typedef struct pointTreeNode{
     TreeNode *node;
     int isVisited;
 }pTreeNode;
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode *node=root;
        stack<pTreeNode*> treeStack;
        vector<int> treeNum;
        pTreeNode *p;
        while(node!=NULL||!treeStack.empty())
        {

            if(node!=NULL)
            {
                p=new pTreeNode();
                p->node=node;
                p->isVisited=1;
                treeStack.push(p);
                node=node->left;
            }
            else
            {
                p=treeStack.top();
                if(p->isVisited==1)
                {
                    node=p->node->right;
                    p->isVisited=2;
                }
                else
                {
                    treeNum.push_back(p->node->val);
                    treeStack.pop();
                }
            }
        }
        return treeNum;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。