LeetCode第897题 – 递增顺序查找树

67 views

题目

给你一个树,请你 按中序遍历 重新排列树,使树中最左边的结点现在是树的根,并且每个结点没有左子结点,只有一个右子结点。

解答

	public void interOrder(TreeNode node, List<TreeNode> nodes) {
		if (node == null) {
			return;
		}

		interOrder(node.left, nodes);

		TreeNode child = new TreeNode(node.val);
		nodes.add(child);

		interOrder(node.right, nodes);
	}

	public TreeNode increasingBST(TreeNode root) {
		if (root == null) {
			return null;
		}

		LinkedList<TreeNode> nodes = new LinkedList<>();
		interOrder(root, nodes);

		TreeNode firstNode = null;
		TreeNode newNode = null;

		while (!nodes.isEmpty()) {
			TreeNode node = nodes.removeFirst();
			if (newNode == null) {
				newNode = node;
				firstNode = node;
				continue;
			}

			newNode.right = node;
			newNode = newNode.right;
		}

		return firstNode;
	}

要点

本题目考察树的定义,理解中序遍历即可完成解答。
基于递归法做出上述解答,同时使用一个列表对象来跟踪遍历过程中记录到对象。
限于时间,暂时没有想到更简洁的方法,比如省略掉记录中序遍历结果的列表。



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第897题 – 递增顺序查找树

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud