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

题目

给定一个二叉树，返回它的前序、中序、后序遍历；

题解

1. 递归法：

class Solution {
   	//递归解法：	//前序遍历     List
   
     arr = new ArrayList<>();     public List
    
      preorderTraversal(TreeNode root) {
            TreeNode head = root;         if(head == null){
                return arr;         }         arr.add(head.val);         preorderTraversal(head.left);         preorderTraversal(head.right);         return arr;     } }
    
   

class Solution {
   	//递归解法	//中序遍历    List
   
     res = new ArrayList<>();    public List
    
      inorderTraversal(TreeNode root) {
           TreeNode head = root;        if(head == null){
               return res;        }        inorderTraversal(root.left);        res.add(head.val);        inorderTraversal(root.right);        return res;    }}
    
   

class Solution {
   	//递归解法	//后序遍历    List
   
     res = new ArrayList<>();    public List
    
      postorderTraversal(TreeNode root) {
           TreeNode head = root;        if(head == null){
               return res;        }        postorderTraversal(head.left);        postorderTraversal(head.right);        res.add(head.val);        return res;    }}
    
   

3. 迭代法：

class Solution {
       //迭代解法：建立一个栈，来存放输出数据    //前序遍历    public List
   
     preorderTraversal(TreeNode root) {
           List
    
      res = new ArrayList<>();        if(root == null){
               return res;        }        Deque
     
       stack = new LinkedList
      
       ();        TreeNode node = root;        while(!stack.isEmpty() || node != null){
               while(node!=null){
                   res.add(node.val);                stack.push(node);                node = node.left;            }            node =stack.pop();            node = node.right;        }        return res;    }}
      
     
    
   

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