背景:
最近在做一些二叉树的编程题的时候,由于牛客网、leetcode这类网站,写算法的时候,只需要你根据参数,返回对应的返回数据类型即可,但是我们在本地ide写代码的时候,可能会需要写main方法,需要输出一些提示信息来调试代码。那么就需要自己的一组数据作为二叉树的输入来建立一颗二叉树,如果自己一个节点一个节点去new效率太低,故需要一个构建方法(但由于个人需求,下面的方法只用来建立一棵二叉排序树)。
思路:
由于大多数题目的输入基本都是按照层次遍历的顺序来输入一组数据的,所以此处只思考创建一颗二叉排序树。故,在递归插入节点的时候,只需要考虑大于根节点的插到右子树,小于根节点的插到左子树即可。
代码实现:
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}public class BinarySearchTree {private TreeNode root;// 插入新值的方法public void insert(int val) {root = insertRec(root, val);}// 递归插入private TreeNode insertRec(TreeNode node, int val) {// 如果树是空的,返回一个新的节点if (node == null) {return new TreeNode(val);}// 否则递归下去if (val < node.val) {node.left = insertRec(node.left, val);} else if (val > node.val) {node.right = insertRec(node.right, val);}// 返回未改变的节点指针return node;}// 创建树的方法public void createTree(int[] values) {for (int val : values) {insert(val);}}// 遍历方法(用于验证树的结构,输出中序遍历)public void inorderTraversal(TreeNode node) {if (node != null) {inorderTraversal(node.left);System.out.print(node.val + " ");inorderTraversal(node.right);}}// 主方法public static void main(String[] args) {BinarySearchTree bst = new BinarySearchTree();int[] values = {5, 3, 7, 2, 4, 6, 8};bst.createTree(values);// 输出中序遍历序列bst.inorderTraversal(bst.root); // 输出应为 2 3 4 5 6 7 8}
}
总结:
这段代码写来仅自用,如有需要,在移植到自己本地的时候需要微调。