由数组构造二叉树
image.png
image.png
思路
1.根节点下标为a,根的左子树下标为b,根的右子树下标为c:b=ax2,c=ax2+1
2.数组中每赋一个给TreeNode,则置0
代码
public static TreeNode buildTree(int[] array,int index){
if(index<array.length){
int value=array[index];
if(value!=0){
TreeNode node=new TreeNode(value);
array[index]=0;
node.left=buildTree(array,index*2);
node.right=buildTree(array,index*2+1);
return node;
}
}
return null;
}
深度优先遍历二叉树
思路
采用递归
1.先序遍历：根左右 1245367
2.中序遍历：左根右 4251637
3.后序遍历：左右根 4526731
代码
//先序，深度优先遍历
public static void fun(TreeNode tree) {
if (tree == null) {
return;
}
System.out.println(tree.val);
if (tree.left != null) {
fun(tree.left);
}
if (tree.right != null) {
fun(tree.right);
}
}
广度优先遍历二叉树
思路
1.利用队列
代码
//广度优先遍历
public static void fun1(TreeNode tree) {
LinkedList<TreeNode> list = new LinkedList<>();
if (tree == null) {
return;
}
list.add(tree);
while (list.size() != 0) {
TreeNode n = list.get(0);
System.out.println(n.val);
list.remove(0);
if (n.left != null) {
list.add(n.left);
}
if (n.right != null) {
list.add(n.right);
}
}
}
