二叉树的基础

这章的代码 点击进入
视频入口 点击进入

先序遍历、中序遍历、后序遍历（递归版）

public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int v){
            this.value = v;
        }
    }
	//先序遍历
    public static void pre(Node head){
        if(head == null) return;
        System.out.println(head);
        pre(head.left);
        pre(head.right);
    }
    //中序遍历
    public static void in(Node head){
        if(head == null) return;
        pre(head.left);
        System.out.println(head);
        pre(head.right);
    }
	//后序遍历
    public static void pos(Node head){
        if(head == null) return;
        pre(head.left);
        pre(head.right);
        System.out.println(head);
    }

何为递归调用（递归序）

先序遍历、中序遍历、后序遍历（非递归版）

先序遍历

思想

1. 将节点压入栈，弹出就打印
2. 如果有右节点，就把右节点压入栈
3. 如果有左节点，就把左节点压入栈

public static void pre1(Node head){
        if(head == null) return;
        if(head != null){
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                head = stack.pop();
                System.out.println(head);
                if(head.right != null){
                    stack.add(head.right);
                }
                if(head.left != null){
                    stack.add(head.left);
                }
            }
        }
    }

后序遍历

思想

1. 和先序遍历差不多，先序遍历是头右左的入栈，而后续则是头左右的顺序

public static void pos1(Node head){
        if(head == null) return;
        if(head != null){
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();

            stack1.add(head);
            while (!stack1.isEmpty()){
                head = stack1.pop();
                stack2.add(head);
                if(head.left != null){
                    stack1.add(head.left);
                }
                if(head.right != null){
                    stack2.add(head.right);
                }
            }
            while (!stack2.isEmpty()){
                System.out.println(stack2.pop());
            }
        }

中序遍历

public static void in1(Node head){
        if(head == null) return;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
                head = stack.pop();
                System.out.println(head);
                head = head.right;
            }
        }
    }

层次遍历

思想：
将数据放入队列中

 public static void level(Node head){
        if(head == null) return ;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.println(cur);
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
    }

求出树中的最大宽度

方法一：

用一个hashMap记录每个节点位于哪个层

 public static int maxWithUseMap(Node head) {
        if (head == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);

        int curLevel = 1; //当前你正在统计哪一层
        int curLevelNodes = 0; //当前层curLevel层的宽度
        int max = 0;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (cur.left != null) {
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
            if (curLevel == curNodeLevel) {
                curLevelNodes++;
            } else {
                max = Math.max(max,curLevelNodes);
                curLevelNodes = 1;
                curLevel ++;
            }
        }
        max = Math.max(curLevelNodes,max);
        return max;
    }

方法二：

不需要用到哈希表的方法

public static int maxWithNoMap(Node head) {
        if (head == null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);

        Node curEnd = head; //当前层的结束节点
        Node nextEnd = null; //下一层最右的节点

        int max = 0;
        int curLevelNodes = 0; //当前层的节点数

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            curLevelNodes++;
            if (cur == curEnd) {
                max = Math.max(max, curLevelNodes);
                curLevelNodes = 0;
                curEnd = nextEnd;
            }
        }

        return max;
    }

树的序列化和反序列化

先序遍历序列化

通过序列化可以还原一棵树

public static Queue<String> preSerial(Node head){
        Queue<String> ans = new LinkedList<>();
        pres(head,ans);
        return ans;
    }

    public static void pres(Node head,Queue<String> ans){
        if(head == null){
            ans.add(null);
        }else{
            ans.add(String.valueOf(head.value));
            pres(head.left,ans);
            pres(head.right,ans);
        }
    }

先序遍历反序列化

public static Node buildByPreQueue(Queue<String> preList){
        if(preList == null || preList.size() == 0) return null;
        return preb(preList);
    }

    public static Node preb(Queue<String> preList){
        String value = preList.poll();
        if(value == null){
            return null;
        }
        Node head = new Node(Integer.parseInt(value));
        head.left = preb(preList);
        head.right = preb(preList);
        return head;
    }

层次遍历序列化

public static Queue<String> levelSerial(Node head){
        Queue<String> ans = new LinkedList<>();
        if(head == null){
            ans.add(null);
        }else{
            ans.add(String.valueOf(head.value));
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()){
                if(head.left != null){
                    ans.add(String.valueOf(head.left));
                    queue.add(head.left);
                }else{
                    ans.add(null);
                }
                if(head.right != null){
                    ans.add(String.valueOf(head.right));
                    queue.add(head.right);
                }else{
                    ans.add(null);
                }
            }
        }
        return ans;
    }

层次遍历反序列化

public static Node buildByLevelQueue(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) {
            return null;
        }
        Node head = generateNode(levelList.poll());
        Queue<Node> queue = new LinkedList<>();
        if (head != null) {
            queue.add(head);
        }
        Node node = null;
        while (!queue.isEmpty()){
            node = queue.poll();
            node.left = generateNode(levelList.poll());
            node.right = generateNode(levelList.poll());
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
        return head;

    }

    public static Node generateNode(String val) {
        if (val == null) return null;
        return new Node(Integer.parseInt(val));
    }

二叉树的递归套路

这章的代码 点击这里

打印二叉树

 public static void printTree(Node head) {
        System.out.println("print Tree: ");
        printInorderTree(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInorderTree(Node head, int height, String to, int len) {
        if (head == null) return;
        printInorderTree(head.right, height + 1, " v ", len);

        //打印的事
        String val = to + head.value + to;
        //保证了所打印的东西再17这个长度中保持最中间的位置
        int lenVal = val.length();
        int lenL = (len - lenVal) / 2;
        int lenR = len - lenVal - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInorderTree(head.left, height + 1, " ^ ", len);
    }

    public static String getSpace(int num) {
        StringBuffer stb = new StringBuffer(" ");
        for (int i = 0; i < num; i++) {
            stb.append(" ");
        }
        return stb.toString();
    }


    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(-222222222);
        head.right = new Node(3);
        head.left.left = new Node(Integer.MIN_VALUE);
        head.right.left = new Node(55555555);
        head.right.right = new Node(66);
        head.left.left.right = new Node(777);
        printTree(head);
    }

后继节点

思想
后继节点是以中序遍历为本的
以根节点和叶子节点为例
根节点的后继节点是右子树的最左的节点
叶子结点的后继节点是跟根据父节点中有无节点是父节点的右节点

 public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int v) {
            this.value = v;
        }
    }

    public static Node getSuccessorNode(Node node){
        if(node == null) return null;
        if(node.right != null){
            return getLeftMost(node.right);
        }else{
            Node parent = node.parent;
            while (parent != null && parent.left != node){
                node = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node){
        if(node == null) return null;
        while (node.left != null){
            node = node.left;
        }
        return node;
    }

对折纸条

public static void printAllFolds(int N){
        printProcess(1,N,true);
    }

//    true 为“凹”，false 为“凸”
    public static void printProcess(int i,int N,boolean down){
        if(i > N) return;
        printProcess(i + 1,N,true);
        System.out.println(down ? "凹" : "凸");
        printProcess(i + 1,N,false);
    }


    public static void main(String[] args) {
        printAllFolds(3);
    }

判断一颗树是否为二叉树

//左右要求一样，Info信息返回的结构体
    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static Info process2(Node x) {
        if(x == null) return new Info(true,0);

        Info leftInfo = process2(x.left);
        Info rightInfo =  process2(x.right);

        int height = Math.max(leftInfo.height,rightInfo.height) + 1;
        boolean isBalanced = true;
        if(!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height - rightInfo.height) > 2){
            isBalanced = false;
        }
        return new Info(isBalanced,height);
    }

    //我主函数只需要知道你是否平衡
    public static boolean isBalanced2(Node head){
        return process2(head).isBalanced;
    }

返回一棵树的最大距离

 public static class Info2 {
        public int maxDistance;
        public int height;

        public Info2(int dis, int h) {
            this.maxDistance = dis;
            this.height = h;
        }
    }

    public static int maxDistance2(Node head) {
        return process3(head).maxDistance;
    }

    public static Info2 process3(Node head) {
        if (head == null) return new Info2(0, 0);
        Info2 left = process3(head.left);
        Info2 right = process3(head.right);

        int height = Math.max(left.height, right.height) + 1;
        int maxDistance = Math.max(Math.max(left.maxDistance, right.maxDistance), left.height + right.height + 1);

        return new Info2(height, maxDistance);
    }

返回一棵二叉树中最大的二叉搜索树的头结点

 public static class Info4 {
        public boolean isBST;
        public int maxSubBSTSize;
        public int min;
        public int max;

        public Info4(boolean is, int size, int mi, int ma) {
            this.isBST = is;
            this.maxSubBSTSize = size;
            this.min = mi;
            this.max = ma;
        }
    }

    public static int maxSubBSTSize2(Node head) {
        if (head == null) return 0;
        return process4(head).maxSubBSTSize;
    }

    public static Info4 process4(Node head) {
        if (head == null) return null;

        Info4 leftInfo = process4(head.left);
        Info4 rightInfo = process4(head.right);


        boolean isBST = false;
        int maxSubBSTSize = 0;

        if (
                (leftInfo == null ? true : leftInfo.isBST)
                        &&
                        (rightInfo == null ? true : rightInfo.isBST)
                        &&
                        (leftInfo == null ? true : leftInfo.max < head.value)
                        &&
                        (rightInfo == null ? true : rightInfo.min > head.value)

        ) {
            maxSubBSTSize =(leftInfo == null ? 0 :leftInfo.maxSubBSTSize ) + (rightInfo.maxSubBSTSize == null ? 0 : rightInfo.maxSubBSTSize) + 1;
            isBST = true;

        }


        if (leftInfo != null) {
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if (rightInfo != null) {
            maxSubBSTSize = Math.max(maxSubBSTSize, rightInfo.maxSubBSTSize);
        }


        int min = head.value;
        int max = head.value;

        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }


        return new Info4(isBST, maxSubBSTSize, min, max);

    }

派对的最大快乐值

这个题因为当时状态不太好，就没有听。