二叉树相关知识

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
    
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

    //前序遍历
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }

        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
	//中序遍历
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
	//后序遍历
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        inOrder(root.right);
        System.out.println(root.val);
    }
	
	//层序遍历
    public void BFSOrder(TreeNode root){
        if (root == null){
            return;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode temp = null;
        queue.offer(root);
        while (!queue.isEmpty()){
            temp = queue.poll();
            System.out.println(temp.val);
            if (temp.left != null){
                queue.offer(temp.left);
            }
            if (temp.right != null){
                queue.offer(temp.right);
            }
        }
    }

    //前序
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || root != null){
            if (root != null){
                list.add(root.val);
                deque.push(root);
                root =root.left;
            }else {
                TreeNode tmp = deque.pop();
                root = tmp.right;
            }
        }
        return list;
    }

	//中序
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || root != null){
            if (root != null){
                deque.push(root);
                root =root.left;
            }else {
                TreeNode tmp = deque.pop();
                list.add(tmp.val);
                root = tmp.right;
            }
        }
        return list;
    }

	//后序  反转前序操作 先添加队首添加节点  先循环右子树  再循环左子树
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        while (!deque.isEmpty() || root != null){
            if (root != null){
                deque.push(root);
                list.add(0,root.val);
                root =root.right;
            }else {
                TreeNode tmp = deque.pop();
                root = tmp.left;
            }
        }
        return list;
    }

public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根结点

    public class BSTNode<T extends Comparable<T>> {
        public T key;                // 关键字(键值)
        public BSTNode<T> left;      // 左孩子
        public BSTNode<T> right;     // 右孩子
        public BSTNode<T> parent;    // 父结点

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
}