与树有关的知识，包括算法

树的基本概念

节点的度

有几个子节点就是有多少度

树的度

节点有几个分叉,度就是几

根节点

一个树的初始节点

子节点

一个节点含有的子树的根节点称为该节点的子节点

叶子节点

没有子节点的节点就叫叶子节点

子树

由某个子节点开始,还包含子节点所构成的树叫做子树(子包含叶子节点也算是子树)

高度,深度

深度：对于任意节点n的深度为从根节点到n的唯一路径长，根节点的深度为0；
高度：对于任意节点n的高度为从n到叶子节点的最长路径长，所有叶子节点的高度为0；

tree_example

二叉树的先序,中序,后序遍历

就是遍历二叉树的时候读取根节点的顺序,叶子节点的遍历顺序永远是从左到右.

先序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点

深度优先遍历,广度优先遍历

广度优先遍历就是按先左后右的顺序，依次把子树依次压入队列，然后来遍历输出
深度优先遍历就是按先右后左的顺序，依次把子树依次压入栈，然后来遍历输出 DFS（深度优先遍历）:ABDECFG

BFS（广度优先遍历）:ABCDEFG

二叉树重建

二叉树只能在提供“前序遍历+中序遍历”或者“后序遍历+中序遍历”这两个组合的其中一个才能进行重建，下面是“前序遍历+中序遍历”重建二叉树的二个算法的代码实现

第一个效率较低，但较直观的算法

给出一个二叉树的前序遍历和中序遍历列表，而且列表中的数字都不是重复的，现要求根据这两个遍历列表推导出该二叉树，前序遍历列表为 [1,2,4,5,3,6,7] ，中序遍历列表为 [4,2,5,1,6,3,7]。

开始分析，根据二叉树的遍历规则，我们第一步可以确定前序遍历列表的第一个元素（数字 1）是该二叉树的根节点，因为前序遍历是从二叉树的根节点开始遍历的，然后又得知该二叉树的节点的值都是不相同的，因此我们在中序遍历列表中找到根节点（数字 1）所在的位置，再结合中序遍历的规则，根节点左侧的为左子树，右侧的为右子树，即把中序遍历列表以根节点（数字 1）为界限分割成两部分，左右两部分分别为二叉树的左右子树。

经过上面的分析我们可以得出在中序遍历列表中左右子树的各节点值，左子树为：[4,2,5]，右子树为：[6,3,7]，也就是说左子树有三个元素，右子树有四个元素，所以同样的，在前序遍历列表中根节点（数字 1）后面的三个数字是其左子树，再后面的就是其右子树了，分别为：[2,4,5] 和 [3,6,7]。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int[] preorder;
    private int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int preS, int preE, int inS, int inE) {
        if (preorder.length == 0) {
            return null;
        }
        if (preS >= preE) {
            return new TreeNode(preorder[preS]);
        }
        for (int i = inS; i <= inE; i++) {
            if (inorder[i] == preorder[preS]) {
                final TreeNode treeNode = new TreeNode(preorder[preS]);
                final int count = i - inS;
                if (count > 0) {
                    treeNode.left = buildTree(preS + 1, preS + count,inS, i - 1);
                }
                if (i < inE) {
                    treeNode.right = buildTree(preS + count + 1, preE,i + 1, inE);
                }
                return treeNode;
            }
        }
        return null;
    }
}

第二个算法效率较高，但是教抽象

先前我们思考的是preorder的第一个元素将inorder划分成了左根右形式，那么inorder的第一个元素在preorder中代表什么？

inorder的第一个元素应该是二叉树最左边元素，那当preorder一直走到其等于inorder[0]时，代表二叉树最左点到达了尽头。
那如何判断最左点右子树情况，最左点到达尽头后，如果其没有右结点，inorder下一个元素就是其父节点的值；反之，inorder下一个值即为右结点，又重复上诉操作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int in = 0;
    private int pre = 0;
    private int[] preorder;
    private int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return build(Integer.MIN_VALUE);
    }

    private TreeNode build(int stop) {
        if (pre >= preorder.length)
            return null;
        if (inorder[in] == stop) {
            in++;
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(node.val);
        node.right = build(stop);
        return node;
    }
}

树与树的遍历