二叉树遍历

public class FristSequenceTraversal {

    // 先序遍历-递归
    public static void  fristSequenceTraversal(Node parent){
        if(parent == null){
            return;
        }
        System.out.print(parent.value);
        System.out.print(" ");
        // 左子树
        fristSequenceTraversal(parent.left);
        // 右子树
        fristSequenceTraversal(parent.right);
    }


    // 先序遍历非递归  根左右
    // 头结点先入栈，弹出就打印，且弹出时，如果有右孩子先加右孩子，在加左孩子
    public static void fristSequenceTraversal2(Node parent){
        if(parent == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(parent);
        while (!stack.isEmpty()){
            // 弹出就打印
            Node cur = stack.pop();
            System.out.print(cur.value);
            System.out.print(" ");
            if(cur.right != null){
                stack.push(cur.right);
            }

            if(cur.left != null){
                stack.push(cur.left);
            }
        }
    }


    // 中序递归
    public static void inSequenceTraversal(Node parent){
        if(parent == null){
            return;
        }
        inSequenceTraversal(parent.left);
        System.out.print(parent.value);
        System.out.print(" ");
        inSequenceTraversal(parent.right);
    }

    // 中序遍历非递归
    public static void inSequenceTraversal2(Node parent){
        if(parent == null){
            return;
        }
        if(parent != null){
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || parent != null){
                if(parent != null){
                    stack.push(parent);
                    parent = parent.left;
                }else{
                    Node cur = stack.pop();
                    System.out.print(cur.value);
                    System.out.print(" ");
                    parent = cur.right;
                }

            }
        }

    }

    // 后续遍历递归
    public static void afterSequenceTraversal(Node parent){
        if(parent == null){
            return;
        }
        afterSequenceTraversal(parent.left);
        afterSequenceTraversal(parent.right);
        System.out.print(parent.value);
        System.out.print(" ");
    }
    // 后续 遍历非递归
    public static void afterSequenceTraversal2(Node parent){
        if(parent == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack.push(parent);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            stack2.push(cur);
            if(cur.left != null){
                stack.push(cur.left);
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
        }

        while (!stack2.isEmpty()){
            System.out.print(stack2.pop().value);
            System.out.print(" ");
        }
    }

    // 层序遍历
    public static void levelSequenceTraversal(Node parent){
        if(parent == null){
            return;
        }
        Queue<Node> queue = new LinkedList();
        queue.offer(parent);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(cur.value);
            System.out.print(" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
}

实现二叉树的按层遍历

public class 按层遍历 {
    public static List<List<Integer>> ceng(Node head){
        List<List<Integer>> res = new ArrayList<>();
        if(head == null){
            return res;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        int size = 1;
        while (!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            for(int i = 0;i < size;i++){
                Node poll = queue.poll();
                temp.add(poll.value);
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
            }
            res.add(temp);
            size = queue.size();
        }
        return res;
    }
}

二叉树序列化

public class TreeSerialization {
   static Queue<Integer> queue  = new LinkedList();

    // 前序遍历序列化
    public static void serialization(Node head){
        if(head == null){
            queue.add(null);
        }else {
            queue.add(head.value);
            serialization(head.left);
            serialization(head.right);
        }
    }

    // 反序列化
    public static Node unSerialization(){
        Integer poll = queue.poll();
        if(poll == null){
            return null;
        }
        Node node = new Node(poll);
        node.left = unSerialization();
        node.right = unSerialization();
        return node;

    }
}

求二叉树最宽的层有多少个节点

  public static int maxNodeNum(Node head){
        if(head == null){
            return 0;
        }

        Queue<Node> queue = new LinkedList<>();

        queue.offer(head);

        int max = 0;
        int curNum = 0;
        Node nextLastNode = null;
        Node curLastNode = head;
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            curNum++;

            if(cur.left != null){
                nextLastNode = cur.left;
                queue.offer(cur.left);
            }

            if(cur.right != null){
                nextLastNode = cur.right;
                queue.offer(cur.right);
            }

            if(cur == curLastNode){
                // 结算
                max = Math.max(max,curNum);
                curLastNode = nextLastNode;

                curNum = 0;
            }
        }
        return max;
    }