結構

class Node{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value = value;
    }
}

二叉樹的遍歷

對于所有子樹來說,遞歸思想
理解:對于所有子樹來說,都要符合某個序遍歷的順序
先序:先頭結點->左子樹->右子樹

/**
     * 先序遍歷
     * @param head
     */
    public void preOrder(Node head){
        if(head == null){
            return;
        }
        System.out.print(head.value+"=>");
        preOrder(head.left);
        preOrder(head.right);
    }

中序:左子樹->頭結點->右子樹

/**
     * 中序遍歷
     * @param head
     */
    public void midOrder(Node head){
        if(head == null){
            return;
        }
        midOrder(head.left);
        System.out.print(head.value+"=>");
        midOrder(head.right);
    }

后序:左子樹->右子樹->頭結點

/**
     * 后序遍歷
     * @param head
     */
    public void posOrder(Node head){
        if(head == null){
            return;
        }
        posOrder(head.left);
        posOrder(head.right);
        System.out.print(head.value+"=>");
    }

遞歸序:根據(jù)遞歸邏輯遍歷了整個樹(每一個節(jié)點都會到達三次)
先序:第一次到達一個節(jié)點打印
中序:第二次到達一個節(jié)點
后序:第三次到達一個節(jié)點

image.png

遞歸序,尋找節(jié)點為(本身節(jié)點->左子節(jié)點->右子節(jié)點)
A->B->D->G->G(G的左子節(jié)點未找到回到G)->G(G的右子節(jié)點未找到回到G)->D->H->H->H->D->B->B->A->C->E->E->I->I->I->E->C->F->F->F->C->A
每一個節(jié)點都到達了三次
先序遍歷(第一次到達節(jié)點打印即為)=A,B,D,G,H,C,E,I,F
中序遍歷(第二次到達節(jié)點打印)=G,D,H,B,A,E,I,C,F
后序遍歷(第三次到達節(jié)點打印)=G,H,D,B,I,E,F,C,A

非遞歸的方式實現(xiàn)先序,中序和后序
1.任何遞歸方式都可以改成非遞歸
2.自己設計壓棧的方式實現(xiàn)

1.先序

1.1利用壓棧方式
1.1彈出就打印
1.2.先右后左(彈出時即先左后右)

/**
 * 先序遍歷(壓棧)
     * @param head
     */
    public void preOrder(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            head = stack.pop();
            System.out.print(head.value + "=>");
            if(head.right != null){
                stack.push(head.right);
            }
            if(head.left != null){
                stack.push(head.left);
            }
        }
    }

實現(xiàn)(后序):
方式1:
1.彈出壓入另一個棧
2.先左后右
3.逆序返回另一個棧
理解:先序為根->右->左進棧,后序為左->右->根進棧,正好為先序棧的逆序情況

/**
     * 后序?qū)崿F(xiàn)1
     * @param head
     */
    public void after1(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> rever = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            head = stack.pop();
            rever.push(head);
            if(head.left != null){
                stack.push(head.left);
            }
            if(head.right != null){
                stack.push(head.right);
            }
        }
        while(!rever.isEmpty()){
            System.out.print(rever.pop().value + "=>");
        }
    }

方式2:
用兩個指針head,cur標記是否左右頭子樹被輸出過了
head指向上次被處理過的節(jié)點

public void after2(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node cur = null;
        while(!stack.isEmpty()){
            cur = stack.peek();
            if(cur.left != null && head != cur.left && head != cur.right){
                stack.push(cur.left);
            }else if(cur.right != null && head != cur.right){
                stack.push(cur.right);
            }else{
                System.out.print(stack.pop().value + "=>");
                head = cur;
            }
        }
    }

實現(xiàn)(中序):
1.整條左邊界依次進棧
2.彈出再進入右節(jié)點
整棵樹可以被左邊界拆解,對于棧中數(shù)據(jù),都是先左后頭

/**
     * 中序遍歷
     * @param head
     */
    public void midOrder(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                System.out.print(cur.value + "=>");
                cur = cur.right;
            }
        }
    }

按層遍歷(寬度優(yōu)先遍歷)
隊列方式:一層一層加,從左到右

/**
     * 按層遍歷二叉樹
     * @param head
     */
    public void fl(Node head){
        if(head == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            head = queue.poll();
            System.out.print(head.value + "=>");
            if(head.left != null){
                queue.add(head.left);
            }
            if(head.right != null){
                queue.add(head.right);
            }
        }
    }

題目:哪一層寬度最大,寬度為多少
解析:
方式1:用map的方式,key是Node,value是哪一層
2.變量哪一層,層寬度,全局最大寬度

/**
     * 求層最大寬度
     * @param head
     */
    public int maxWidth(Node head){
        if(head == null){
            throw new RuntimeException("二叉樹為空");
        }
        //層最大寬度
        int max = 0;
        //key=node,value=node所在的層
        Map<Node,Integer> map = new HashMap<>();
        map.put(head,1);
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        //當前所在哪一層
        int curLevel = 1;
        //當前層的最大寬度
        int curLevelWidth = 0;
        while(!queue.isEmpty()){
            head = queue.poll();
            //此節(jié)點在哪一層
            int curNodeLevel = map.get(head);
            if (head.left != null){
                map.put(head.left,curNodeLevel + 1);
                queue.add(head.left);
            }
            if (head.right != null){
                map.put(head.right,curNodeLevel + 1);
                queue.add(head.right);
            }
            //如果還在當前層,寬度就++
            if(curLevel == curNodeLevel){
                curLevelWidth++;
            }else{//如果不在當前層,說明將進入下一層,比較記錄當前層的最大寬度與整體最大寬度
                max = Math.max(curLevelWidth,max);
                curLevel++;
                curLevelWidth = 1;
            }
        }
        return max;
    }

方式二:1.當前層最右節(jié)點
2.下一層最右節(jié)點
3.每一個節(jié)點找下一層的最右節(jié)點

/**
     * 不使用map求層最大寬度
     * @param head
     */
    public int maxWidthNoMap(Node head){
        if(head == null){
            throw new RuntimeException("二叉樹不存在");
        }
        int max = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        //當前層最右節(jié)點
        Node curEnd = head;
        //下一層最右節(jié)點
        Node nextEnd = head;
        //層寬
        int curNodeWidth = 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;
            }
            curNodeWidth++;
            //如果已經(jīng)到了當前層最右節(jié)點,則進行結算
            if (cur == curEnd){
                max = Math.max(max,curNodeWidth);
                //重置當前層最右節(jié)點到下一層最右節(jié)點
                curEnd = nextEnd;
                curNodeWidth = 0;
            }
        }
        return max;
    }

二叉樹的序列化和反序列化

1,可以用先序和后序遍歷,實現(xiàn)序列化(需要加空節(jié)點)
2.反序列化同理
3.中序方式則不行
如:

*         __2
*        /
*       1
*       和
*       1__
*          \
*           2
補足空位置的中序遍歷結果都是{ null, 1, null, 2, null}

public Queue<Node> serializble(Node head){
        if(head == null){
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        serialerByPreOrder(head,queue);
        return queue;
    }

    /**
     * 先序方式進行序列化二叉樹
     * @param head
     * @param queue
     */
    private void serialerByPreOrder(Node head, Queue<Node> queue) {
        if(head == null){
            queue.add(head);
            return;
        }
        queue.add(head);
        serialerByPreOrder(head.left,queue);
        serialerByPreOrder(head.right,queue);
    }

先序方式進行反序列化
后序方式進行反序列化,需將nodes列表中的節(jié)點放入棧中,用棧來實現(xiàn)序列化

/**
     * 先序方式進行反序列化
     * @param nodes
     * @return
     */
    public Node buildByPreOrder(Queue<Node> nodes){
        if (nodes == null || nodes.size() == 0){
            return null;
        }
        Node head = preb(nodes);
        return head;
    }

    private Node preb(Queue<Node> nodes) {
        Node poll = nodes.poll();
        if (poll == null){
            return null;
        }
        poll.left = preb(nodes);
        poll.right = preb(nodes);
        return poll;
    }

后序方式反序列化

public Node buildByPosOrder(Queue<Integer> nodes){
        if(nodes == null || nodes.size() == 0){
            return null;
        }
        //先序為 頭->左->右 放入棧中彈出即為 右->左->頭
        Stack<Integer> stack = new Stack<>();
        while(!nodes.isEmpty()){
            stack.add(nodes.poll());
        }
        Node head = prob(stack);
        return head;
    }

    private Node prob(Stack<Integer> stack) {
        Integer pop = stack.pop();
        if(pop == null){
            return null;
        }
        //彈出 右->左的順序,設置也先設置右,后設置左
        Node head = new Node(pop);
        head.right = prob(stack);
        head.left = prob(stack);
        return head;
    }

按層序列化

public Queue<Node> serializer(Node head){
        if(head == null){
            return null;
        }
        //用戶按層遍歷的隊列
        Queue<Node> queue = new LinkedList<>();
        //序列化后的隊列
        Queue<Node> nodes = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            //從層隊列彈出放入序列化隊列
            Node poll = queue.poll();
            nodes.add(poll);
            //如果poll為null,說明沒有節(jié)點,繼續(xù)彈出
            while (poll == null && !queue.isEmpty()){
                poll = queue.poll();
                nodes.add(poll);
            }
            //隊列彈空還為null,說明到了最后一個節(jié)點,直接跳出
            if (poll == null){
                break;
            }
            queue.add(poll.left);
            queue.add(poll.right);
        }
        return nodes;
    }

按層進行反序列化

/**
     * 按層進行反序列化
     * @param levelList
     * @return
     */
    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<Node>();
        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.valueOf(val));
    }