L2-004 这是二叉搜索树吗?(Java)

2024-03-28数据结构与算法2 分钟117 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

题目

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

  • 其左子树中所有结点的键值小于该结点的键值;
  • 其右子树中所有结点的键值大于等于该结点的键值;
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式:
输入的第一行给出正整数 N(≤1000){N(\leq1000)}。随后一行给出 N{N} 个整数键值,其间以空格分隔。

输出格式:
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO。

输入样例 1:

sh 复制代码
7
8 6 5 7 10 8 11

输出样例 1:

sh 复制代码
YES
5 7 6 8 11 10 8

输入样例 2:

sh 复制代码
7
8 10 11 8 6 7 5

输出样例 2:

sh 复制代码
YES
11 8 10 7 5 6 8

输入样例 3:

sh 复制代码
7
8 6 8 5 10 9 11

输出样例 3:

sh 复制代码
NO
sh 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

题解

我们知道,前序遍历的顺序是根左右,而二叉搜索树的左节点值肯定比根节点的小,而右节点的值肯定比根节点的大或者相等,题目中的前序遍历可能是镜像后的结果,那么就反过来,左节点的大于等于根节点的值,右节点的小于根节点的值。根据这种思路,我们就可以利用这一特性,去构建这颗二叉树,并判断其结果是否满足要求。

java 复制代码
import java.util.*;

// L2-004 这是二叉搜索树吗?
public class Main {

	static int[] preorder;

	// 对于任一结点,
	// 其左子树中所有结点的键值小于该结点的键值;
	// 其右子树中所有结点的键值大于等于该结点的键值;
	// 其左右子树都是二叉搜索树。
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		preorder = new int[n];
		// 原前序串
		StringBuilder orignStr = new StringBuilder();
		for (int i = 0; i < n; i++) {
			preorder[i] = sc.nextInt();
			orignStr = orignStr.append(preorder[i] + " ");
		}
		TreeNode3 root = new TreeNode3(preorder[0]);
		// 根据前序遍历
		initSearchTree(root, n);
		// 7
		// 8 6 5 7 10 8 11
		StringBuilder preStr = new StringBuilder();
		pre(root, preStr);
		if (preStr.toString().trim().equals(orignStr.toString().trim())) {
			System.out.println("YES");
			// YES
			// 5 7 6 8 11 10 8
			StringBuilder postStr = new StringBuilder();
			post(root, postStr);
			System.out.println(postStr.toString().trim());
		} else {
			System.out.println("NO");
		}

	}

	/**
	 * 初始化二叉搜索树
	 * 
	 * @param root
	 */
	private static void initSearchTree(TreeNode3 root, int n) {
		// 左节点一定比根节点小
		boolean flag = true;
		if (preorder.length > 1) {
			flag = preorder[0] > preorder[1];
		}
        for (int i = 1; i < n; i++) {
			int val = preorder[i];
			TreeNode3 node = new TreeNode3(val);
			// 每次从根节点加入
			TreeNode3 temp = root;
			while (true) {
				// 不是镜像
				if (flag) {
					if (val >= temp.val) {
						if (temp.right != null) {
							temp = temp.right;
							continue;
						}
						temp.right = node;
						break;
					} else {
						if (temp.left != null) {
							temp = temp.left;
							continue;
						}
						temp.left = node;
						break;
					}
				} else {
					// 镜像
					if (val >= temp.val) {
						if (temp.left != null) {
							temp = temp.left;
							continue;
						}
						temp.left = node;
						break;
					} else {
						if (temp.right != null) {
							temp = temp.right;
							continue;
						}
						temp.right = node;
						break;
					}
				}
			}

		}
	}

	/**
	 * 前序遍历
	 * 
	 * @param root
	 * @param sb
	 */
	private static void pre(TreeNode3 root, StringBuilder sb) {
		if (root == null) {
			return;
		}
		sb = sb.append(root.val + " ");
		if (root.left != null) {
			pre(root.left, sb);
		}
		if (root.right != null) {
			pre(root.right, sb);
		}
	}

	/**
	 * 后续遍历
	 * 
	 * @param root
	 * @param sb
	 */
	private static void post(TreeNode3 root, StringBuilder sb) {
		if (root == null) {
			return;
		}
		if (root.left != null) {
			post(root.left, sb);
		}
		if (root.right != null) {
			post(root.right, sb);
		}
		sb = sb.append(root.val + " ");
	}
}

class TreeNode3 {
	int val;
	TreeNode3 left;
	TreeNode3 right;

	public TreeNode3(int val) {
		this.val = val;
	}
}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句