二叉树的遍历，递归和非递归

向右看齐 2024-04-17 05:44 94阅读 0赞

1，中序遍历

非递归版本，借助一个辅助

vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
    	TreeNode *node = root;
    	stack<TreeNode *> mstack;
    	while(node != NULL || !mstack.empty())
    	{
    	while(node != NULL)
    	{
    	    mstack.push(node); // 注意这里入栈不能写指针，写结点
    	    node = node->left;
    	}
    
    		ans.push_back(mstack.top()->val); // 注意这里是 .
    		node = mstack.top()->right;
    		mstack.pop(); 
    	}
    	return ans;
    }

递归版本，简洁

vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) 
    {
    	if(root != NULL)
    	{
    	    inorderTraversal(root->left);
    	    ans.push_back(root->val);
    	    inorderTraversal(root->right);
    	}
        
      return ans;
    }

2，二叉树的后续遍历

非递归版本，后续遍历稍微麻烦点，通过设置一个 “前一个节点”变量，来记录下一次应该访问的结点

vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) 
    {
    	if(root == NULL) 
    		return ans;
    
    	stack<TreeNode*> mstack;
    	TreeNode* pre = NULL; //前一个节点
    	while(!mstack.empty()|| root != NULL)
    	{
    		if(root != NULL)
    		{
    			mstack.push(root);
    			root = root->left;
    		}
    		else
    		{
    			root=mstack.top();
    			if(root->right == NULL || root->right == pre)
    			{
    				//如果右子树不存在，则接下来该访问根节点。
    				mstack.pop();
    				ans.push_back(root->val);
    				pre = root;
    				root = NULL;
    			}
    			else
    			{
    				//否则柚子树存在，就先访问右子树
    				pre = NULL;
    				root = root->right;
    			}
    		}
    	}
    	return ans;
    }

递归版本，简洁

vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root != NULL)
        {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            ans.push_back(root->val);
        }
        return ans;
    }