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

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

二叉树后序遍历

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

在这里插入图片描述
上图是一棵二叉树，后序遍历结果：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:
      vectorv;
      vector preorderTraversal(TreeNode       root) {
      if(root !=NULL){
      1.   inorderTraversal(root->left)；
      2.   inorderTraversal(root->right);
      3.   v.push_back(root->val);
      4.  }
      5.  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 postorderTraversal(TreeNode       root) {
      stack s;
      TreeNode cur = root;
      TreeNode       last = NULL; // 上一个被完整后序遍历过的树的根结点
      vectorv;
      while (cur != NULL || !s.empty()) {

      1.  while (cur != NULL) {
      2.      s.push(cur);
      3.      cur = cur->left;
      4.  }
      6.  TreeNode *top = s.top();
      7.  if (top->right == NULL) {
      8.      v.push_back(top->val);
      9.      s.pop();
      10.      last = top;
      11.  }
      12.  else if (top->right == last) {
      13.      v.push_back(top->val);
      14.      s.pop();
      15.      last = top;
      16.  }
      17.  else {
      18.      cur = top->right;
      19.  }

      }

      1.  return v;

      }
      };

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

All OVER

发表评论

表情：
评论列表 （有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读