问题描述
给定一个二叉树，返回它的 后序 遍历。示例:
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题目代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
}
}
思路解析
首先需要了解前序,中序,后序遍历的方法.
前序遍历(先序遍历):根结点→左子树→右子树
中序遍历:左子树→根结点→右子树
后序遍历左子树→右子树→根结点
也可以这样理解,前中后(根)遍历.即根结点的访问位置,
前序就是先访问根结点,后依次左右.中序就是根结点再中间位置访问
代码演示
class Solution {
List<Integer> list = new ArrayList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
if (root != null) {
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
}
return list;
}
}扩展
当要求写前序遍历的代码时,只需更改一个位置即可.
list.add(root.val);
前序的话
if (root != null) {
list.add(root.val);
postorderTraversal(root.left);
postorderTraversal(root.right);
}
中序
if (root != null) {
postorderTraversal(root.left);
list.add(root.val);
postorderTraversal(root.right);
}