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);}