剑指offer面试题6 重建二叉树

这篇具有很好参考价值的文章主要介绍了剑指offer面试题6 重建二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

考察点

知识点

链表中每个结点最少有1个指针,最多2(双重链表),前后结点是一对一的关系,而树中每个结点指针数量可以更多一些,也就是说树中的结点存储着更多其它结点的信息,前后结点是一对多的关系(其中靠前的结点有个专门的术语叫父结点,靠后的结点都是孩子结点,没有孩子结点的叫叶子结点,没有父结点的叫根结点)。这俩个数据结构需要解决的问题不一样。依据每个结点包含的指针数量的不同对树做了一些分类,比如每个结点最多包含俩个指针的树叫做二叉树(这里又给这些结点起了个名字二叉树中偏左的叫左结点偏右的叫右结点)
同其它类型的数据结构有一样,树的操作也无外乎创建结点,删除结点,遍历结点,其中创建和删除的过程又都需要用到遍历,遍历一颗普通的树需要O(n),遍历的方式包括前序遍历(根结点-左结点-右结点),中序遍历(左结点-根结点-右结点),后序遍历(左结点-右结点-根结点),遍历的代码实现包括递归和迭代俩种方式,下面代码中有实现。其实递归就是用了程序自己的栈,迭代是用了我们自己创建的栈。
数据结构的目的肯定是为了更高效的使用数据,基于树的这种结构,如果把比父结点小的数据都存左边,比父结点大的数据都存右边,这样查找数据的时候就有点类似于二分查找了,时间复杂度降到O(logn),这样的树被称作搜索树

题目

分析
本题目输入的一个树的前序和中序遍历序列,要求把这颗树重建起来。这里需要了解到程序中有个特别重要的思维叫递归,递归是分层的,每一层的问题都是一样的,只不过问题的规模不一样,面对这类复杂问题你的思考方式一定是2点:1.问题该如何定义?第n层该如何解决?如果第n层的问题已经解决好了,那么就继续用第n层的方式去解决第n-1层;2.第0层的问题是怎么样的该怎么解决。套到这个题目中问题显然就是用一个前序序列和一个中序序列构建树,(1思维展现)第n层问题怎么解决?前序遍历第一个元素就是根结点,而中序遍历左根右如果能找到根结点在中序序列中的位置,那么就能确定该根结点左边的所有结点都是左子树的中序序列,右边的所有结点都是右子树的中序序列,结点数目知道了以后再返回前序遍历找出左子树的前序序列和右子树的前序序列,这样一来就可以继续用这个方法去分别构建左子树和右子树。(2思维展现)第0层肯定是问题规模最小的那一层,本题目中即只有一个结点的时候,这种情况直接解决本层问题就可以了。文章来源地址https://www.toymoban.com/news/detail-801751.html

public class Node{
	int val;
	Node leftChild;
	Node rightChild;

	public Node(int data) {
		this.val = data;
		this.leftChild = null;
		this.rightChild = null;
	}
}
import java.util.Deque;
import java.util.LinkedList;

public class BinaryTree {
	Node root;

	public BinaryTree() {
		this.root = null;
	}
	public void insertTree(int val) {
		if (this.root == null) {
			Node root = new Node(val);
			this.root = root;
		} else {
			insertChildTree(this.root,val);
		}
	}
	public void insertChildTree(Node node,int val) {
		if (node != null && val < node.val) {
			if (node.leftChild == null) {
				node.leftChild = new Node(val);
			} else {
				insertChildTree(node.leftChild,val);
			}
		}
		if (node != null && val > node.val) {
			if (node.rightChild == null) {
				node.rightChild = new Node(val);
			} else {
				insertChildTree(node.rightChild,val);
			}
		}
	}
	public Node getRoot() {
		return this.root;
	}
	public void prePrint(Node node) {
		if (node == null) {
			return;
		}
		System.out.print(node.val + " ");
		prePrint(node.leftChild);
		prePrint(node.rightChild);
	}
	public void midPrint(Node node) {
		if (node == null) {
			return;
		}
		midPrint(node.leftChild);
		System.out.print(node.val + " ");
		midPrint(node.rightChild);
	}
	public void afterPrint(Node node) {
		if (node == null) {
			return;
		}
		afterPrint(node.leftChild);
		afterPrint(node.rightChild);
		System.out.print(node.val + " ");
	}
	public void prePrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				System.out.print(node.val + " ");
				stack.push(node);
				node = node.leftChild;
			}
			if (stack.size() > 0) {
				node = stack.peek().rightChild;
				stack.pop();

			}
		}
	}
	public void midPrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				stack.push(node);
				node = node.leftChild;
			}
			//执行到此说明左子树都已入栈
			if (stack.size() > 0) {
				Node parent = stack.peek();//父结点
				System.out.print(parent.val + " ");
				node = parent.rightChild;
				stack.pop();
			}
		}
	}
	public void afterPrintIteration(Node root) {
		Deque<Node> stack = new LinkedList<>();
		Node pre = null;
		Node node = root;
		while (stack.size() > 0 || node != null) {
			while (node != null) {
				stack.push(node);
				node = node.leftChild;
			}
			Node parent = stack.peek();
			if (parent.rightChild == pre || parent.rightChild == null) {
				System.out.print(parent.val + " ");
				pre = parent;
				stack.pop();
			} else {
				node = parent.rightChild;
			}
		}
	}
	public void constructPrint(int[] pre,int[] mid) {
		if (pre.length != mid.length || pre.length <= 0) {
			throw new Error("params error");
		}
		int len = pre.length;
		Node root = constructTree(pre,0,len-1,mid,0,len-1);
		prePrint(root);
		System.out.println();
		midPrint(root);
		System.out.println();
	}
	public Node constructTree(int[] pre,int preStart,int preEnd,int[] mid,int midStart,int midEnd) {
		int rootVal = pre[preStart];
		Node root = new Node(rootVal);
		root.leftChild = null;
		root.rightChild = null;
		if (preStart == preEnd && midStart == midEnd) {
			if (pre[preStart] != mid[midStart]) {
				throw new Error("input error");
			} else {
				return root;
			}
		}

		int leftMidEnd = midStart;
		for (int i = midStart;i <= midEnd; i++) {
			if (rootVal != mid[i]) {
				leftMidEnd ++;
			} else {
				break;
			}
		}
		//根结点在中序序列中不存在
		if (leftMidEnd > midEnd) {
			throw new Error("input error");
		}
		int leftLength = leftMidEnd - midStart;
		if (leftLength > 0) {
			root.leftChild = constructTree(pre,preStart + 1,preStart + leftLength,mid,midStart,leftMidEnd - 1);
		}
		if (leftLength < midEnd - midStart) {
			root.rightChild = constructTree(pre,preStart + leftLength + 1,preEnd,mid,leftMidEnd + 1,midEnd);
		}
		return root;
	}
}
public class Six {
	public static void main(String[] args) {
		//树的遍历
		BinaryTree tree = new BinaryTree();
		tree.insertTree(10);
		tree.insertTree(6);
		tree.insertTree(14);
		tree.insertTree(4);
		tree.insertTree(8);
		tree.insertTree(12);
		tree.insertTree(16);
		tree.prePrint(tree.getRoot());
		System.out.println();
		tree.prePrintIteration(tree.getRoot());
		System.out.println();
		tree.midPrint(tree.getRoot());
		System.out.println();
		tree.midPrintIteration(tree.getRoot());
		System.out.println();
		tree.afterPrint(tree.getRoot());
		System.out.println();
		tree.afterPrintIteration(tree.getRoot());
		System.out.println();
		int[] pre = {1,2,4,7,3,5,6,8};
		int[] mid = {4,7,2,1,5,3,8,6};
		//本题目重建二叉树
		BinaryTree treeBuild = new BinaryTree();
		treeBuild.constructPrint(pre,mid);
	}
}

到了这里,关于剑指offer面试题6 重建二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode-每日一题【剑指 Offer 27. 二叉树的镜像】

    请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入:      4    /     2     7  /   / 1   3 6   9 镜像输出:      4    /     7     2  /   / 9   6 3   1 示例 1: 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 限制: 0 = 节点个数 = 1000 1.题目要求我们设

    2024年02月13日
    浏览(41)
  • (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    难度:简单 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入: 镜像输出: 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制 : 0 = 节点个数 = 1000 注意 :本题与 226. 翻转二叉树 相同。 💡思路:递归 我们从根节点开始,递归地对树进行遍历: 如果

    2024年02月13日
    浏览(33)
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III

    目录 使用函数实现 使用双端队列实现 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。 例如: 给定二叉树:  [3,9,20,null,null,15,7] , 返回其层次遍历结果:

    2024年02月11日
    浏览(43)
  • 分冶算法 剑指 07 重建二叉树 排序算法:剑指45 把数组排成最小的数 10-I 斐波那契数列

    来记录几个注意事项 1.vector容器里利用find()函数 不同于map(map有find方法),vector本身是没有find这一方法,其find是依靠algorithm来实现的。 所以要包含头文件 另外返回类型并不是int 类型的索引 iterator迭代器类型的 2.关于在vector容器里根据找寻到的位置进行切片,前面为新

    2024年02月15日
    浏览(38)
  • Leetcode-每日一题【剑指 Offer 32 - I. 从上到下打印二叉树】

    从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树:  [3,9,20,null,null,15,7] ,     3    /   9  20     /     15   7 返回: [3,9,20,15,7] 提示: 节点总数 = 1000 1.题目要求我们从上到下打印出二叉树的每个节点,同一层的节点按照从左

    2024年02月12日
    浏览(47)
  • (树) 剑指 Offer 32 - I. 从上到下打印二叉树 ——【Leetcode每日一题】

    难度:中等 从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 返回: 提示 : 节点总数 = 100 💡思路:BFS 使用 优先队列 进行 层序遍历 即可! 🍁代码:(C++、Java) C++ Java 🚀 运行结果: 🕔 复杂度分析: 时间

    2024年02月14日
    浏览(37)
  • Leetcode-每日一题【剑指 Offer 34. 二叉树中和为某一值的路径】

    给你二叉树的根节点  root  和一个整数目标和  targetSum  ,找出所有  从根节点到叶子节点  路径总和等于给定目标和的路径。 叶子节点  是指没有子节点的节点。 示例 1: 输入: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出: [[5,4,11,2],[5,8,4,5]] 示例 2: 输入: ro

    2024年02月11日
    浏览(39)
  • Leetcode-每日一题【剑指 Offer 32 - II. 从上到下打印二叉树 II】

    从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 例如: 给定二叉树:  [3,9,20,null,null,15,7] ,     3    /   9  20     /     15   7 返回其层次遍历结果: [   [3],   [9,20],   [15,7] ] 提示: 节点总数 = 1000 1.题目要求我们从上到下按层打印二

    2024年02月12日
    浏览(43)
  • (树) 剑指 Offer 34. 二叉树中和为某一值的路径 ——【Leetcode每日一题】

    难度:中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]] 示例 2: 输入:roo

    2024年02月13日
    浏览(38)
  • Leetcode-每日一题【剑指 Offer 32 - III. 从上到下打印二叉树 III】

    请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。 例如: 给定二叉树:  [3,9,20,null,null,15,7] ,     3    /   9  20     /     15   7 返回其层次遍历结果:

    2024年02月12日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包