實現一個AI大模型當前都無法正確實現的基礎二叉樹讀取算法

概述

圖1:?

圖2:

上圖幫大家溫習完全二叉樹的概念，本文講的是完全順序二叉樹的初始化

華為的員工、考過華為OD的員工、參加過其他類似大廠的考試的員工一般做過二叉樹的初始化，甚至有些還碰到過手撕代碼時面試官要求做二叉樹遍歷，看完本文的讀者，我相信一定能拿到比較高的評分（盡管手撕的時候面試官一般不會要你關心二叉樹的動態構造，只要寫初始化一個固定的樹跑過測試就行）。

對華為或華為OD感興趣的同學可以參看文章：

華為OD入門級、工作級、專業級技術技能知識點要求及職級薪資表

Java初始化順序二叉樹?

百度AI初始化順序二叉樹

?百度AI生成的代碼分析：

1、buildTree方法明顯邏輯錯誤

理由：左節點如果是index*2+1，那么根節點就應該是0，而實際root又是用1初始化的。

其他的我就不詳細分析了，核心邏輯都錯了結果一定也是錯的

讀者可以親自在百度上試驗。并在本地用其代碼驗證。

作者初始化順序二叉樹

在這之前先給大家看一下我們傳奇人物塔子哥的題庫中的這一道題：

完全二叉樹非葉子部分后序遍歷(100分) - Problem Detail - CodeFun2000

可能需要付費，不過沒關系作者截圖出來：

?額，作者代碼注釋中也有原題，下面看作者代碼實現：

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;/*** @Description: #P2988. 完全二叉樹非葉子部分后序遍歷(100分*
給定一個以順序儲存結構存儲整數值的完全二叉樹序列（最多1000個整數），請找出此完全二叉樹的所有非葉子節點部分，然后采用后序遍歷方式將此部分樹（不包含葉子）輸出。
只有一個節點的樹，此節點認定為根節點（非葉子）。
此完全二叉樹并非滿二叉樹，可能存在倒數第二層出現葉子或者無右葉子的情況
其他說明：二叉樹的后序遍歷是基于根來說的，遍歷順序為：左-右-根輸入描述
一個通過空格分割的整數序列字符串
輸出描述
非葉子部分樹結構。備注：輸出數字以空格分隔樣例1
輸入
1 2 3 4 5 6 7
輸出
2 3 1
說明
找到非葉子部分樹結構，然后采用后序遍歷輸出。1/    \2       3/  \      /  \4     5     6     7/  \   /  \  /  \    /  \8   9  10 11 12  13  14  15* @Author: Dand* @CreateDate: 2025/6/22 22:06* @Version: 1.0*/
public class Main {public static void main(String args[]){Scanner sc = new Scanner(System.in);int[] arr= Arrays.stream(sc.nextLine().split("\\ ")).mapToInt(Integer::parseInt).toArray();Node root = new Root(arr);// 后序遍歷Stack<Node> stack = new Stack<Node>();while (true){if (root != null){stack.push(root);root = root.getLeft();} else {if (stack.isEmpty())return;if (null == stack.peek().getRight()) {// 葉子root = stack.pop();
//                    System.out.print(root.getData() + " ");  // 不打葉子while (root == stack.peek().getRight()) {root = stack.pop();System.out.print(root.getData() + " ");  // 只打非葉子if (stack.isEmpty()) {break;}}}if (!stack.isEmpty())root = stack.peek().getRight();elseroot = null;}}}
}class Node<T> {public T data;public Node<T> left;public Node<T> right;Node(T e){data = e;}public T getData() {return data;}public void setData(T data) {this.data = data;}public Node<T> getLeft() {return left;}public Node<T> getRight() {return right;}public void setLeft(Node<T> node){this.left = node;}public void setRight(Node<T> node){this.right = node;}
}class Root extends Node {public Integer data;public Node<Integer> left;public Node<Integer> right;Root(int[] arr){// size 一定要大于0super(arr[0]);int size = arr.length;if (size > 0) {data = arr[0]; // 根節點是數組第一個值buildTree( this, 1, size , arr);}}/**** @param node* @param index 從1開始* @param size* @param arr*/private void buildTree(Node node, int index, int size, int[] arr) {if ( index * 2 <= size ) {node.left = new Node(arr[index * 2-1] ); // 左子節點值是 2*index + 1buildTree( node.left, index * 2, size, arr ); // 遞歸構建左子樹if (index * 2 + 1 <= size) { // 如果有右子節點node.right = new Node(arr[index * 2] ); // 右子節點值是2*index + 2buildTree( node.right, index * 2 + 1, size, arr ); // 遞歸構建右子樹}}}
}

代碼走讀：

1、作者將用戶輸入讀入int[]中

2、實際輸入不一定是連續的數字

3、如果是連續數字這行用值 index*2初始化即可

node.left = new Node(arr[index * 2-1] );?

因數組索引是0開始，所以以第1個左子節點為例：第2個節點值在整型數組中的索引就是1，遵循AI開始的邏輯，構建ROOT的子樹時傳的index為1，所以上面 index * 2-1剛好是1（輸入的數組中第二個數：arr[index * 2-1]）

4、作者樹采用先創建了一個能用的父類，不用場景可實現不同的子類

5、本題中data只是個簡單的整型值，解決實際問題（如saas平臺健康度的決策樹，因然健康度一般為多叉樹，邏輯有些不一樣，也差不了多少）時讀者可以把子類中的data換成數據對象

6、本題要求后序遍歷，所以作者使用棧實現了后序遍歷

7、相比遞歸，棧占用更少的cpu和內存。

8、本題要求不打印葉子，所以只要注釋掉內部while循環前的那邊打印語句

               if (null == stack.peek().getRight()) {// 葉子root = stack.pop();
//                    System.out.print(root.getData() + " ");  // 不打葉子while (root == stack.peek().getRight()) {root = stack.pop();System.out.print(root.getData() + " ");  // 只打非葉子if (stack.isEmpty()) {break;}}}

遞歸

簡單

先序

    /*** 遞歸先序遍歷* @param root*/private void priOrderWithRecursion(BinaryTreeNode root) {if (null != root) {System.out.print(root.getValue() + "\t");priOrderWithRecursion(root.getLeftChild());priOrderWithRecursion(root.getRightChild());}}

后序

    /*** 遞歸后序遍歷* @param root*/private void postOrderWithRecursion(BinaryTreeNode root) {if (null != root) {postOrderWithRecursion(root.getLeftChild());postOrderWithRecursion(root.getRightChild());System.out.print(root.getValue()+ "\t");}}

中序

    /*** 遞歸中序遍歷* @param root*/private void inOrderWithRecursion(BinaryTreeNode root) {if (null != root) {inOrderWithRecursion(root.getLeftChild());System.out.print(root.getValue() + "\t");inOrderWithRecursion(root.getRightChild());}}

棧（非遞歸）

占更少的計算資源，更好的性能?

先序

    /*** 非遞歸先序遍歷，雖然是采用棧的方式，但是并未完全應用棧的思想，采取循環過程中輸出的方式來遍歷* @param root*/private void preOrder(BinaryTreeNode root) {Stack<BinaryTreeNode> stack = new Stack<>();while (null != root || !stack.isEmpty()) {while (null != root) {System.out.print(root.getValue() + "\t");stack.push(root);root = root.getLeftChild();}if (!stack.isEmpty()) {root = stack.pop();root = root.getRightChild();}}}

后序

見上面作者初始化順序二叉樹? 章節的代碼（包含了后序遍歷）。

中序

    /*** 非遞歸中序遍歷* @param root*/private void inOrder(BinaryTreeNode root) {Stack<BinaryTreeNode> stack = new Stack<>();while (null != root || !stack.isEmpty()) {while (null != root) {stack.push(root);root = root.getLeftChild();}if (!stack.isEmpty()) {root = stack.pop();System.out.print(root.getValue() + "\t");root = root.getRightChild();}}}