68.Binary Tree Postorder Traversal-二叉树的后序遍历（容易题）

本文主要是介绍68.Binary Tree Postorder Traversal-二叉树的后序遍历（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的后序遍历

1. 题目

   给出一棵二叉树，返回其节点值的后序遍历。

2. 样例

   给出一棵二叉树 {1,#,2,3},

   1
   \
   2
   /
   3
   返回 [3,2,1]

3. 挑战

   你能使用非递归实现么？

4. 题解

1.递归法

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/private ArrayList<Integer> result = new ArrayList<Integer>();public ArrayList<Integer> postorderTraversal(TreeNode root) {if (root == null){return result;}postorderTraversal(root.left);postorderTraversal(root.right);result.add(root.val);return result;}
}

2.非递归法
后序遍历的规则是首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子节点，然后遍历右子节点，最后遍历根结点。由于非递归算法利用栈回退到根节点时，并不知道被弹栈的是左子节点还是右子节点。因为如果从左子节点回退到根节点，此时就应该去访问右子节点，而如果从右子节点回退到根节点，此时就应该访问根节点，导致该非递归算法最为复杂。

遍历规则：
1.对于任一结点P，将其入栈后，如果P无子节点或其左、右子节点都已访问就可直接访问P。
2.如果不满足条件1，则将P的右子节点和左子节点依次入栈，以保证将P弹栈的时候，P的左子节点在右子节点可以先于P被访问。

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/public ArrayList<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<>();if (root == null){return result;}stack.push(root);TreeNode p_child = null;TreeNode P = null;while (!stack.empty()){P = stack.peek();if ((P.left == null && P.right == null) || (p_child != null && (p_child == P.left || p_child == P.right))){result.add(P.val);stack.pop();p_child = P;}else{if (P.right != null){stack.push(P.right);}if (P.left != null){stack.push(P.left);}}}return result;}
}

Last Update 2016.8.30

这篇关于68.Binary Tree Postorder Traversal-二叉树的后序遍历（容易题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---