LeetCode中二叉树的前序、中序、后序遍历题解

题目

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

题解

1. 递归法：

 class Solution {
    //递归解法：
    //前序遍历
     List<Integer> arr = new ArrayList<>();
     public List<Integer> 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<Integer> res = new ArrayList<>();
    public List<Integer> 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<Integer> res = new ArrayList<>();
    public List<Integer> 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        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;
    }

}