数组二叉树最小节点 简书
描述:
以数组来存储二叉树,现给定一个数组
树的根节点的值储存在下标 1, 对于储存在下标 n 的节点,
他的左子节点和右子节点分别储存在下标 2*n 和 2*n+1
并且我们用-1 代表一个节点为空
试求从根节点到最小叶子节点的路径,路径由节点的值组成
思路:
将给定的数组先转换为二叉树 ,转换时添加一个向上的 parent
指针指向父节点
层序遍历所有节点,找出最小的叶节点(左右孩子为空的节点则为
叶子节点)
以最小节点开始通过 parent 指针将沿途的所有结点 push 栈,逆
序打印即可
第一步. 根据给定的数组生成二叉树(将字符串切分,0 不可用)
String str = "0 5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6 3";
String str = "0 3 5 7 -1 -1 2 4";
public static Node generateTree(String[] arr){
if(arr == null || arr.length == 0){
return null;