二叉树前序、中序、后序以及层次遍历

前序遍历(中左右)

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while(root != null||!deque.isEmpty()){
            while(root!=null){
                res.add(root.val);
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            root = root.right;
        }
        return res;
    }
}

递归实现前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        order(root,res);
        return res;
    }

    private void order(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }

        res.add(root.val);
        order(root.left,res);
        order(root.right,res);
    }
}

中序遍历(左中右)

/**
 * 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<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while(root != null||!deque.isEmpty()){
            while(root!=null){
                deque.push(root);
                root = root.left;
            }
            res.add(root.val);
            root = deque.pop();
            root = root.right;
        }
        return res;
    }
}

递归实现中序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        order(root,res);
        return res;
    }

    private void order(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        order(root.left,res);
        res.add(root.val);
        order(root.right,res);
    }
}

后序遍历(左右中)

/**
 * 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<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode prev = null;
        while(root!=null||!deque.isEmpty()){
            while(root!=null){
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                deque.push(root);
                root = root.right;
            }
        }
        return res;
    }
}

递归实现后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        order(root,res);
        return res;
    }

    private void order(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        order(root.left,res);
        order(root.right,res);
        res.add(root.val);
    }
}

层次遍历(本质是广度优先搜索)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root == null){
            return res;
        }

        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> aver = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                aver.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(aver);
        }
        return res;
    }
}