二叉树的后序遍历（递归与非递归）

ゝ一世哀愁。 2022-04-24 07:54 235阅读 0赞

## 二叉树后序遍历 ##

介绍了二叉树的先序以及中序遍历，那么我简单的再给大家介绍了一下二叉树的后序遍历。  
请看大屏幕 。。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]  
上图是一棵二叉树，后序遍历结果：4 5 2 6 3 1  
同理，我想你可能会问什么叫做后序遍历，其实很简单，就是按照 左 -》 右 -》 根 的方式去遍历二叉树。

*  首先让我们来看看如何递归的去后序遍历二叉树  
    **注：在这里我特别强调一点，在我们二叉树中，如果采用递归的方式，大部分都采用的根左右的方式，即采用子问题的方式，即先处理跟节点，再处理左子树，再处理右子树的这样一种思想**
 *  后序递归遍历

/**
     * 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>v;
        vector<int> preorderTraversal(TreeNode* root) {
          if(root !=NULL){
             inorderTraversal(root->left)；
             inorderTraversal(root->right);
             v.push_back(root->val);
            }
            return v;
        }
    };

你没看错，代码还是这么简单，但是如何递归的你得想清楚，这里我就不做详解了。那么接下来我们再看看非递归的方式

*  后序非递归遍历

/**
     * 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 *> s;
    	TreeNode *cur = root;
    	TreeNode *last = NULL;		// 上一个被完整后序遍历过的树的根结点
        vector<int>v;
    	while (cur != NULL || !s.empty()) {
    		while (cur != NULL) {
    			s.push(cur);
    			cur = cur->left;
    		}
    
    		TreeNode *top = s.top();
    		if (top->right == NULL) {
    			v.push_back(top->val);
    			s.pop();
    			last = top;
    		}
    		else if (top->right == last) {
    			v.push_back(top->val);
    			s.pop();
    			last = top;
    		}
    		else {
    			cur = top->right;
    		}
    	}
            return v;
        }
    };

这就是后序遍历的非递归方式，这种方式主要是采用栈来完成的，相对而言，我觉得非递归后序遍历二叉树比先序以及中序较难，它会在第三次遇到节点时处理节点。

**All OVER**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220217/227705aa02f446269dcdc3c6150e2cc0.png