二叉树

一、二叉树的遍历概念

1. 二叉树的遍历是指从根结点触发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

(1) 前(先)序遍历

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子书。

特点：① 根----->左------->右 ② 根据前序遍历的结果可知第一个访问的必定是root结点。

(2) 中序遍历

中序遍历：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

特点：① 左----->根------->右

② 根据中序遍历的结果，再结合前序遍历的root结点去划分root结点的左右子树。

(3) 后序遍历

后序遍历：若二叉树为空，则空操作返回，否则从左到右先叶子结点后结点的方式遍历访问左右子树，最后访问根结点。

特点：① 左------>右------>根

② 根据后序遍历的结果可知最后访问的必定是root结点。

(4) 层序遍历

层序遍历：若二叉树为空，则空返回，否则从树的第一层，即根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

特点：①. 从左到右，从上到下

②. 可知第一个访问的必定是root结点

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
 
    public TreeNode() {
    }
 
    public TreeNode(int val) {
        this.val = val;
    }
 
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}