当前位置：首页 > news >正文

实现一个AI大模型当前都无法正确实现的基础二叉树读取算法

news 2025/6/29 12:21:35

概述

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