Day9 25/2/22 SAT

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358

5、二叉树

5.0 二叉树节点结构

5.1 前序/中序/后序遍历 & 递归/非递归实现

5.1.1 前序/中序/后序遍历区分

5.1.2 递归实现

5.1.3 非递归实现

5.2 直观地打印一棵二叉树

5.3 二叉树的宽度优先遍历

5.4 二叉树类型判断

二叉搜索树

完全二叉树

真二叉树

满二叉树

平衡二叉树

笔记：

5、二叉树

5.0 二叉树节点结构

class Node<V>{
    V calue;
    Node left;
    Node right;
}

5.1 前序/中序/后序遍历 & 递归/非递归实现

5.1.1 前序/中序/后序遍历区分

在二叉树中，遍历的顺序指的是访问节点的顺序：

前序遍历（Pre-order Traversal）：根节点 -> 左子树 -> 右子树。

中序遍历（In-order Traversal）：左子树 -> 根节点 -> 右子树。

后序遍历（Post-order Traversal）：左子树 -> 右子树 -> 根节点。

主要区别在于根节点的访问时机：

前序遍历最先访问根节点。

中序遍历，根节点在左右子树都访问完成后才被访问。

后序遍历最后访问根节点。

5.1.2 递归实现

class Node<V>{
    V calue;
    Node left;
    Node right;
}

// 前序遍历
public void preOrder(Node root) {
    if (root == null) return;
    System.out.print(root.val + " ");  // 先访问根节点
    preOrder(root.left);               // 再遍历左子树
    preOrder(root.right);              // 最后遍历右子树
}

// 中序遍历
public void inOrder(Node root) {
    if (root == null) return;
    inOrder(root.left);                // 先遍历左子树
    System.out.print(root.val + " ");  // 再访问根节点
    inOrder(root.right);               // 最后遍历右子树
}

//后序遍历
public void postOrder(Node root) {
    if (root == null) return;
    postOrder(root.left);              // 先遍历左子树
    postOrder(root.right);             // 再遍历右子树
    System.out.print(root.val + " ");  // 最后访问根节点
}

5.1.3 非递归实现

任何递归函数都可以改成非递归函数，相当于不让系统自动压入栈，而是自己手动压入栈。栈是先进后出的。

前序遍历中，遍历顺序为“头左右”（头节点、左子节点、右子节点），操作：

step 1. 从栈中弹出一个节点N

step 2. 找到它的左、右子节点

step 3. 先压入栈右子节点，再压入左子节点（这样先弹出左子节点，再弹出右子节点）

public static void preorder(Node node){
    if(node != null){
        Stack<Node> stack = new Stack<Node>();
        stack.add(node);

        while( !stack.isEmpty() ){
            node = stack.pop();
            System.out.print(node.value + “ ”);
            if( node.right != null)stack.push(node.right);
            if( node.left != null)stack.push(node.left);
        }
    }
}

中序遍历中，遍历顺序为“左头右”（左子节点、头节点、右子节点），操作：

public static void inorder(Node node){
    if(node != null){
        Stack<Node> stack = new Stack<Node>();
        while( !stack.isEmpty() || node != null ){
            if( node != null){
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                System.out.print(node.value + “ ”);
                node = node.right;
            }
        }
    }
}

后序遍历中，遍历顺序为“左右头”（左子节点、右子节点、头节点），操作：

public static void postorder(Node node){
    if(node != null){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(node);
        
        while( !s1.isEmpty() ){
            node = s1.pop();
            s2.push(node);
            if( node.left!= null)s1.push(node.left);
            if( node.right!= null)s1.push(node.right);
        }
        while( !s2.isEmpty() ) System.out.print(s2.pop().value + “ ”);
    }
}

5.2 直观地打印一棵二叉树

class BinaryTreePrinter {
    // 打印二叉树的结构
    static void printTree(TreeNode root) {
        printTree(root, "", true);
    }

    // 辅助方法：递归打印每层节点
    private static void printTree(TreeNode node, String indent, boolean last) {
        if (node != null) {
            System.out.println(indent + (last ? "└── " : "├── ") + node.val);
            indent += last ? "    " : "│   ";
            printTree(node.left, indent, false);  // 打印左子树
            printTree(node.right, indent, true);  // 打印右子树
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        
        printTree(root);
    }
}

5.3 二叉树的宽度优先遍历

常见题目：求一颗二叉树的宽度，也就是树的每层最多存在了几个节点。

可以采用队列Queue进行辅助，队列的特性是先进先出。遍历完一层后要遍历下一层的节点时，每次弹出一个节点，再把它的左右子节点推进队列。

public static void broadReversal(Node node) {
        if (node == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        int maxWidth = 0;

        // 广度优先遍历
        while (!queue.isEmpty()) {
            // 获取当前层的节点数
            int levelSize = queue.size();
            maxWidth = Math.max(maxWidth, levelSize); // 更新最大宽度

            // 遍历当前层
            for (int i = 0; i < levelSize; i++) {
                Node current = queue.poll();
                System.out.print(current.value + " "); // 输出当前节点的值

                // 将左右子节点加入队列
                if (current.left != null) queue.add(current.left);
                if (current.right != null) queue.add(current.right);
            }
            System.out.println(); // 换行，表示一层的结束
        }

        System.out.println("Maximum width of the binary tree is: " + maxWidth);
    }