数据结构-二叉树

什么是二叉树？

对于每个父节点来说，最多有俩个孩子节点，分别为左孩子节点和右边孩子节点。没有父节点的节点叫跟节点，没有孩子节点的节点叫叶子节点。

怎么确定二叉树？

根据前序和中序来重建二叉树

前序遍历数组的第一个节点即为根节点的信息，在中序遍历数组中查找到根节点的位置，根节点的左边是左子树，跟节点的右边是右子树，这样我们就可以得到左子树的中序遍历，右子树的中序遍历。

根据上一步得到左子树和右子树的长度，截取出前序遍历的左字数前序遍历，右子树前序遍历。依次类推，通过递归的方式，我们就能够构建出二叉树。

根据中序和后序来重建二叉树？

后序遍历数组的最后一个节点即为根节点的信息，在中序遍历数组中查找到根节点的位置，根节点的左边是左子树，跟节点的右边是右子树，这样我们就可以得到左子树的中序遍历，右子树的中序遍历。

根据上一步得到左子树和右子树的长度，截取出后序遍历的左字树后序遍历，右子树后序遍历。依次类推，通过递归的方式，我们就能够构建出二叉树。

为什么前序和后序确定不了二叉树的结构？

因为前序 和 后序遍历只能确定一棵二叉树的根节点 和 左右子树有哪些节点，而左右子树的具体结构并不能确定。

二叉树

如图所示，图片中的俩棵二叉树的前序遍历都为123，后序遍历都为321。

二叉树的遍历

前序遍历

对于一个二叉树来言，前序遍历 是先遍历父节点，然后再遍历左孩子节点，然后遍历右孩子节点。这里需要注意的是，如果左孩子节点还有孩子节点或者右孩子还有孩子节点，则按照上面的规则再依次遍历。

中序遍历

对于一个二叉树来言，中序遍历 是先遍历左孩子节点，然后再遍历父节点，然后遍历右孩子节点。这里需要注意的是，如果左孩子节点还有孩子节点或者右孩子还有孩子节点，则按照上面的规则再依次遍历。

后序遍历

对于一个二叉树来言，后序遍历 是先遍历左孩子节点，然后再遍历右孩子节点，然后遍历父节点。这里需要注意的是，如果左孩子节点还有孩子节点或者右孩子还有孩子节点，则按照上面的规则再依次遍历。

实战题目

1. 牛客网-重建二叉树

博主微信公众号

<img src="https://gitee.com/chenhaogit/blogimages/raw/master/xsj/wzgzh-8cm.jpg" style="float:right"/>