若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。

1.介绍

二叉树的后序遍历是一种遍历二叉树的策略，按照"左子树-》右子树-》根节点"的顺序访问节点的子树或根节点。具体来说，后序遍历首先访问左子树，然后访问右子树，最后访问根节点。

这种遍历方式在编程中可以通过递归或非递归的方式进行实现。

通常来说，递归算法较容易理解，但可能会造成栈溢出，而非递归算法较难理解。

以下用代码实现后序遍历。

2.代码

以下以Java编程语言为例。

1）二叉树节点的数据结构定义如下：

class TreeNode {  int value;  TreeNode left;  TreeNode right;  TreeNode(int value) {  	this.value = value;  }}

2）后序遍历递归算法代码

public void postOrderTraversalRecursive(TreeNode root){  //若root节点为空，则子遍历完成  if(null==root){  	return ;  }  //先递归遍历左子树  postOrderTraversalRecursive(root.left);  //再递归遍历右子树  postOrderTraversalRecursive(root.right);  //最后访问根节点  System.out.println(root.value);}

3）后序遍历非递归算法代码（单栈法）

可以使用栈来模拟递归过程。此例只用到了一个栈，所以叫做单栈法。

后序遍历与前序遍历和中序遍历存在差异。即我们在访问左子树之后需要访问右子树，然后才能再访问根节点，所以我们的根节点不能在访问左子树之后出栈，而是需要继续访问右子树，当我们右子树访问完成之后再出栈。

public void postOrderTraversalNonRecursive(TreeNode root){  //存储遍历过程中的需要继续处理的临时节点  Stack<TreeNode> stack = new Stack<>();  //保存临时根节点，从root开始  TreeNode node =root;  //保存上次访问的节点，从root开始  TreeNode lastVisit = root;  //临时节点不为空或者栈不为空时需要继续处理  while(null != node || !stack.empty())  {    while(null != node){      //存储临时节点到栈中      stack.push(node);      //继续遍历左子树      node = node.left;    }  //查看当前栈顶元素  node = stack.peek();  //如果当前栈顶元素的右子树为空，或者右子树已经被访问，则说明左右节点都访问完成了  //则可以直接输出当前节点的值  if(null == node.right || node.right==lastVisit){    //左子树与右子树都访问完成后输出当前根节点的值    System.out.println(node.value+" ");    //当前节点已处理完成，从栈中弹出，继续下一轮遍历    stack.pop();    //更新上次访问的节点    lastVisit=node;    //左子树右子树根节点都访问完毕后，将临时节点置空，从而从栈中处理下一个节点    node=null;  }else{    //右子树尚未被访问，则继续遍历右子树    node=node.right;  }  }}

4）后序遍历非递归算法代码（双栈法）

由于后序遍历的输出顺序是左->右->根，倒过来就是根->右->左。因此利用栈（先进后出FILO，与正常顺序是反的）的性质，只需要按照根->右->左的访问顺序访问一次，并存入栈中，最后从栈顶输出所有栈节点就可以了。

算法需要两个栈，一个是正常遍历需要的栈，一个是存储倒过来的元素的栈，所以也叫双栈法。

public static void postOrderTraversalNonRecursive2Stack(TreeNode root) {  //后序遍历中存储正常访问顺序的栈  Stack<TreeNode> stack = new Stack<TreeNode>();  //后序遍历中存储逆向访问顺序的栈  Stack<TreeNode> output = new Stack<TreeNode>();  TreeNode node = root;  //判断是否还有节点需要处理  while (null != node || !stack.isEmpty()) {    if (null != node) {      //先访问根节点，压入栈中      stack.push(node);      output.push(node);      //再访问右子节点      node = node.right;    } else {      //再访问左子节点      node = stack.pop();      node = node.left;    }  }  //从栈顶开始输出栈里元素的值，即输出正常访问顺序栈stack的倒序结果output栈，即为最终结果  while (output.size() > 0) {    TreeNode n = output.pop();    System.out.print(n.value + " ");  }}

5）后序遍历非递归算法代码（Stack+Deque，即栈+双向队列法）

算法的数据结构里，一个存储正常遍历需要的栈，一个存储最终输出的元素双端队列列表，所以也叫栈+双向队列法。

public List<TreeNode> postOrderTraversalNonRecursiveStackDeque(TreeNode root) {  //保存计算出的最终结果列表  LinkedList<TreeNode> result = new LinkedList<>();  //若root节点为空，则遍历完成  if (null == root) {  	return result;  }  //后序遍历中存储正常访问顺序的栈  Stack<TreeNode> stack = new Stack<>();  //压入根节点到栈中  stack.push(root);  //存储当前节点  TreeNode curNode;  //若栈中有数据，则继续处理  while(!stack.isEmpty()) {     //获取当前栈顶元素    curNode = stack.pop();    //将栈顶元素插入到结果列表LinkedList的头部    result.addFirst(curNode.value);    if (null != curNode.left) {      //压入左子节点到栈中      stack.push(curNode.left);    }    if (null != curNode.right) {      //压入右子节点到栈中      stack.push(curNode.right);    }  }  return result;}

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。