本文共 1950 字，大约阅读时间需要 6 分钟。

题目描述：

标签：栈  树 

给定一个二叉树，返回它的 后序 遍历。

 代码：

思路分析：后序遍历是左子树-右子树-根。思路同。

《方法一：递归》 

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public List
   
     postorderTraversal(TreeNode root) {        List
    
      list = new ArrayList
     
      ();        postorder(root,list);        return list;    }    public void postorder(TreeNode root,List
      
        res){        if(root == null){            return;        }        postorder(root.left,res);        postorder(root.right,res);        res.add(root.val);    }}
      
     
    
   

《方法二：迭代》

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public List
   
     postorderTraversal(TreeNode root) {        List
    
      list = new ArrayList
     
      ();        if(root == null){            return list;        }        Deque
      
        stack = new LinkedList
       
        ();        TreeNode prev = null;        while(root != null || !stack.isEmpty()){            while(root != null){                stack.push(root);                root = root.left;            }            root = stack.pop();            if(root.right == null || root.right == prev){                list.add(root.val);                prev = root;                root = null;            }else{                stack.push(root);                root = root.right;            }        }        return list;    }}
       
      
     
    
   

转载地址：http://ppdhz.baihongyu.com/