二叉树数据结构

  由于在LeetCode上刷题时遇到二叉树的问题都会非常头疼，因为二叉树的数据结构在本机没有实现。因此此类编程题目无法在本机进行运行，更无法改错啦！为了解决这个麻烦，于是自己简单实现了一个二叉树的数据结构，构造参数通过Object数组进行初始化。toString()中集成了层序遍历、前序遍历、中序遍历和后序遍历。

前序遍历

采用递归法进行前序遍历

    private List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(root,list);
        return list;
    }
    private void preorder(TreeNode root,List<Integer> list) {
        if(root != null){
            list.add(root.val);
            preorder(root.left,list);
            preorder(root.right,list);
        }
    }

中序遍历

采用迭代法+栈进行中序遍历

    private List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        if(root==null)return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty()|| cur != null){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }

后序遍历

采用迭代法+自定义数据结构Command进行后续遍历

    private List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        if(root==null)return list;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go",root));
        while (!stack.isEmpty()){
            Command cur = stack.pop();
            if(cur.message.equals("print")){
                list.add(cur.node.val);
            }else{
                stack.push(new Command("print",cur.node));
                if(cur.node.right!=null)stack.push(new Command("go",cur.node.right));
                if(cur.node.left!=null)stack.push(new Command("go",cur.node.left));
            }

        }
        return list;
    }
    /**
     * @Author CourageHe
     * @Description  后续遍历的辅助数据结构，可通过Pair代替
     * @Date 2020/6/9 0:33
     **/
    private class Command {
        String message;
        TreeNode node;
        Command(String message, TreeNode node) { this.message = message;this.node = node;}
    }

层序遍历

采用迭代法+队列 进行层序遍历

    private List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();

        Queue<Pair<TreeNode,Integer>> queue = new ArrayDeque<>();
        queue.add(new Pair<>(root,0));

        while (!queue.isEmpty()){
            TreeNode node = queue.peek().getKey();
            int level = queue.peek().getValue();
            queue.poll();
            //如果节点为空，则跳过
            if(node == null) continue;
            //如果该层没有列表 则新建
            if(level == list.size())
                list.add(new ArrayList<>());

            list.get(level).add(node.val);
            queue.add(new Pair<>(node.left,level+1));
            queue.add(new Pair<>(node.right,level+1));
        }
        return list;
    }

完整代码

import javafx.util.Pair;

import java.util.*;

public class TreeNode {

    public int val;
    public TreeNode left;
    public TreeNode right;

    private Queue<TreeNode> queue = new ArrayDeque<>();


    public TreeNode(int x) {
        val = x;
    }

    //根据n个元素的数组arr创建一个链表
    //使用arr为参数，创建另外一个listnode的构造函数
    public TreeNode(Object[] arr) {
        this.val = (int)arr[0];
        TreeNode cur = this;
        for (int i = 1; i < arr.length; i+=2) {
            if(arr[i] != null ){
                cur.left = new TreeNode((int)arr[i]);
                queue.add(cur.left);
            }
            if(arr[i+1] != null ){
                cur.right = new TreeNode((int)arr[i+1]);
                queue.add(cur.right);
            }
            cur = queue.poll();
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append("层序遍历："+levelOrder(this)+"\n");
        s.append("前序遍历："+preorderTraversal(this)+"\n");
        s.append("中序遍历："+inorderTraversal(this)+"\n");
        s.append("后序遍历："+postorderTraversal(this)+"\n");

        return s.toString();
    }
    /**
     * @Author CourageHe
     * @Description 树的层序遍历
     * @Date 2020/6/9 0:09
     * @Param [root]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    private List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();

        Queue<Pair<TreeNode,Integer>> queue = new ArrayDeque<>();
        queue.add(new Pair<>(root,0));

        while (!queue.isEmpty()){
            TreeNode node = queue.peek().getKey();
            int level = queue.peek().getValue();
            queue.poll();
            //如果节点为空，则跳过
            if(node == null) continue;
            //如果该层没有列表 则新建
            if(level == list.size())
                list.add(new ArrayList<>());

            list.get(level).add(node.val);
            queue.add(new Pair<>(node.left,level+1));
            queue.add(new Pair<>(node.right,level+1));
        }
        return list;
    }


    /**
     * @Author CourageHe
     * @Description 树的前序遍历
     * @Date 2020/6/9 0:14
     * @Param [root]
     * @return java.util.List<java.lang.Integer>
     **/
    private List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preorder(root,list);
        return list;
    }
    private void preorder(TreeNode root,List<Integer> list) {
        if(root != null){
            list.add(root.val);
            preorder(root.left,list);
            preorder(root.right,list);
        }
    }

    /**
     * @Author CourageHe
     * @Description  中序遍历
     * @Date 2020/6/9 0:29
     * @Param [root]
     * @return java.util.List<java.lang.Integer>
     **/
    private List<Integer> inorderTraversal(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        if(root==null)return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty()|| cur != null){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }


    /**
     * @Author CourageHe
     * @Description 树的后序遍历
     * @Date 2020/6/9 0:31
     * @Param [root]
     * @return java.util.List<java.lang.Integer>
     **/
    private List<Integer> postorderTraversal(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        if(root==null)return list;
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go",root));
        while (!stack.isEmpty()){
            Command cur = stack.pop();
            if(cur.message.equals("print")){
                list.add(cur.node.val);
            }else{
                stack.push(new Command("print",cur.node));
                if(cur.node.right!=null)stack.push(new Command("go",cur.node.right));
                if(cur.node.left!=null)stack.push(new Command("go",cur.node.left));
            }

        }
        return list;
    }
    /**
     * @Author CourageHe
     * @Description  后续遍历的辅助数据结构，可通过Pair代替
     * @Date 2020/6/9 0:33
     **/
    private class Command {
        String message;
        TreeNode node;
        Command(String message, TreeNode node) { 
            this.message = message;this.node = node;
        }
    }

    public static void main(String[] args) {
        Object []arr = {3,9,20,null,null,15,7};
        TreeNode root = new TreeNode(arr);
        System.out.println(root);
    }


}