一、问题描述

画二叉树的时候，总是无法对齐圆点得到对称的节点。例如：

graph test {
    graph [dpi=80]
    node [shape=circle];

    1 -- 2, 3;
    2 -- 4, 5 [color=red,penwidth=3.0];

    3 -- 6, 7 [color=red,penwidth=3.0];
    4 -- 8;
}

画出来的效果：

红色标出来的4个线条，长度不一样，子节点看起来不对称，就导致整个二叉树看起来也不够美观。

二、解决方案

可以在子节点中加一个中间节点，把线条的weight设置成10，然后隐藏中间的节点和连线：

graph bin_tree {
    node [shape=circle];

    1 -- 2, 3;
    2 -- 4;
    // 隐藏中间节点的连线
    2 -- m2 [weight=10 style="dashed"];
    2 -- 5;

    3 -- 6;
    // 隐藏中间节点的连线
    3 -- m3 [weight=10 style="dashed"];
    3 -- 7;
    4 -- 8;
        
        // 隐藏中间节点
    m2, m3 [label="" style="dashed"]
}

效果：

weight属性的作用是设置线条的权重，权重越大，线条越垂直。

如果希望完全隐藏中间节点，只要把对应节点和线条的属性设置为invis即可：

style="dashed" -> style="invis"

三、参考

Enforcing horizontal node ordering in a .dot tree

How to get balanced diagrams from graphviz?

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出前序遍历 preorder = [3,9,20,15,7]，中序遍历 inorder = [9,3,15,20,7]，返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

二、题解

这道题在《剑指offer》也出现了，题目完全一样。主要用到了树的两个特性：

• 前序遍历的首元素为根节点。
• 中序遍历中，根节点的左边是左子树，根节点的右边是右子树。

解题的思路就是：通过前序遍历得到根节点，然后在中序遍历中找到这个节点，再通过递归的方式找出左右子树。

详细的分析可以参考《剑指offer》面试题7：重建二叉树。

三、代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        size_t len = preorder.size();
        if (len < 1)
            return nullptr;
        return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);        
    }
private:
    TreeNode *buildTreeCore(vector<int> &preOrder, unsigned int preStart, unsigned int preEnd,
                            vector<int> &inOrder, unsigned int inStart, unsigned int inEnd) {
        unsigned int idx, lchild_len;
        TreeNode *root = nullptr;
        root = new TreeNode(preOrder[preStart]);

        if (preStart == preEnd) {
            return root;
        }

        // 在中序遍历中找到根节点
        idx = inStart;
        while (idx < inEnd && root->val != inOrder[idx]) {
            idx++;
        }

        // 左子树的长度
        lchild_len = idx - inStart;
        
        if (lchild_len > 0) {
            // 计算左子树
            root->left = buildTreeCore(preOrder, preStart + 1, preStart + lchild_len,
                    inOrder, inStart, idx - 1);
        }

        if (lchild_len < preEnd - preStart) {
            // 计算右子树
            root->right = buildTreeCore(preOrder, preStart + lchild_len + 1, preEnd,
                    inOrder, idx + 1, inEnd);
        }

        return root;
    }
};

执行通过：

一、题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如，输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6]，则重建如下图所示的二叉树并输出它的头结点：

二、解析

根据前序、中序遍历的特性和上面的图形能得到的结论：

• 前序遍历的第一个元素就是树的根节点。
• 根节点左边的元素就是左子树，根右边的就是右子树。

图片描述：

基于这两个特性就可以通过以下方式来构建出一颗二叉树：从前序遍历中确认根节点，再到中序遍历中找到定位到这个根节点，这样就可以拿到对应的左子树和右子树了。然后再按照相同的方式分别得到左右子树的子树，那么整个二叉树就可以构建起来了。

三、代码实现

二叉树节点定义：

template<typename T>
class tree_node {
    friend class bin_tree<T>;
    tree_node(const T &data) : data(data), lchild(nullptr), rchild(nullptr) {}
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
}

二叉树定义：

class bin_tree {
public:
    bin_tree() : root(nullptr) {}
    tree_node<T> *root;
};

在二叉树类中实现通过前序遍历和中序遍历构造二叉树的函数：

/*
 * 根据前序和中序遍历序列构造一个二叉树
 * @pre_order 前序遍历序列
 * @in_order 中序遍历序列
 * @len 序列长度
 */
void construct(const T pre_order[], const T in_order[], const unsigned int len) {
    if (len < 1)
        return;

    this->root = construct_core(pre_order, pre_order + len - 1, 
            in_order, in_order + len - 1);
}

/*
 * 通过前序遍列和中序遍历的结果构建二叉树
 * 前序遍历序列[pre_order_start, pre_order_end]，中序遍历序列[in_order_start, in_order_end]
 * @pre_order_start 前序遍历的开始位置
 * @pre_order_end 前序遍历的结束位置
 * @in_order_start 中序遍历的开始位置
 * @in_order_end 中序遍历的结束位置
 */
tree_node<T> *construct_core(const T *pre_order_start, const T *pre_order_end,
                             const T *in_order_start, const T *in_order_end) {
    // 遍历指针
    const T *cursor;
    // 前序遍历序列中左子树的结束位置
    const T *lchild_end;
    // 左子树的长度
    unsigned int lchild_len;
    // 根节点
    tree_node<T> *root = nullptr;;

    // 前序遍历的首元素即为树根
    root = new tree_node<T>(pre_order_start[0]);

    // 如果前序遍历的头和尾相等，说明只有一个元素了，返回当前元素
    if (pre_order_start == pre_order_end) {
        // 下面是简单的判断输入参数是否合法
        // 如果只有一个元素了，前序和中序的遍历结果是相同的
        if (in_order_start == in_order_end && *in_order_start == *pre_order_start)
            return root;
        else // 输入有问题
            throw "invalid input";
    }

    // 在中序遍历中找到根节点
    cursor = in_order_start;
    while (cursor < in_order_end && *cursor != root->data)
        cursor++;

    // 匹配到中序遍历的最后一个元素了还没有找到，说明输入不合法
    if (cursor == in_order_end && *cursor != root->data)
        throw "invalid input";

    lchild_len = cursor - in_order_start;
    lchild_end = pre_order_start + lchild_len;

    // 递归获取左子树
    if (lchild_len > 0) {
        root->lchild = construct_core(pre_order_start + 1, lchild_end,
                                      in_order_start, cursor - 1);
    }

    // 递归获取右子树
    if (lchild_len < pre_order_end - pre_order_start) {
        root->rchild = construct_core(lchild_end + 1, pre_order_end,
                                      cursor + 1, in_order_end);
    }

    return root;
}

四、单元测试

单元测试覆盖以下几点：

• 树为空
• 树只有一个节点
• 完全二叉树
• 满二叉树
• 不完全二叉树

4.1 树为空

/*
 * 测试：通过前序和中序遍历序列构造二叉树
 * 案例：二叉树为空
 */
TEST(construct_by_pre_order_and_in_order, no_node) {
    bin_tree<int> tree;
    tree.construct(nullptr, nullptr, 0);
    EXPECT_FALSE(tree.get_root());
}

4.2 树只有一个节点

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：二叉树包含一个节点
 */
TEST(construct_by_pre_order_and_in_order, one_node) {
    bin_tree<int> tree;
    int data[1] = {1};
    tree.construct(data, data, 1);
    EXPECT_TRUE(tree.get_root());
    EXPECT_FALSE(tree.get_root()->get_lchild());
    EXPECT_FALSE(tree.get_root()->get_rchild());
}

4.3 完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：完全二叉树测试
 *          1
 *        2   3
 *       4 5
 */
TEST(construct_by_pre_order_and_in_order, complete_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3};
    int in_order[7] = {4, 2, 5, 1, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
}

4.4 满二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：满二叉树测试
 *          1
 *        2   3
 *       4 5 6 7
 */
TEST(construct_by_pre_order_and_in_order, full_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3, 6, 7};
    int in_order[7] = {4, 2, 5, 1, 6, 3, 7};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 7);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    EXPECT_EQ(node->get_rchild()->get_data(), 7);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());
}

4.5 非完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：普通二叉树测试
 *          1
 *        2   3
 *         5 6
 */
TEST(construct_by_pre_order_and_in_order, normal_bin_tree) {
    int pre_order[7] = {1, 2, 5, 3, 6};
    int in_order[7] = {2, 5, 1, 6, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
    // 左子节点为6，右子节点为空
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
}

4.6 测试结果

一、梳排序简介

梳排序是冒泡排序的一种优化方案，主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据，先进行部分优化，然后逐步减少步长，以此来对数据进行预处理。

以数组[3,1 5, 2, 4]为例，假设步长是2，那么就分别处理[3, 5, 4]和[1, 2]，先局部优化。优化完成后，再使用冒泡排序。

关于步长的选取

步长并不是逐步递减的，步长的选取一般通过一个步长因子来控制：

1. 初始化时，步长等于数组长度除以步长因子。
2. 后续的所有步长都等于前一次步长除以步长因子，直到步长小于等于1。

从实验结果来看，这个步长因子设置为1.3时能获得较好的性能，并且实验数据证明，梳排序的良好性能甚至可以与快速排序媲美。

排序示例

以数组[41, 11, 18, 7, 16, 25, 4, 23, 32, 31, 22, 9, 1, 22, 3, 7, 31, 6, 10]为例，它的长度是19，计算得到的步长分别是[14, 10, 7, 5, 3, 2]，它的预处理过程可以整理为：

其中no表示第几趟排序，step表示步长，data是当前经过处理后的数组。很明显可以看出经过6次预处理后，数据已经基本有序了。

此时再通过冒泡排序来对整体排序就能减少很多工作量了（实际上只需要再做一次冒泡排序就能完成排序了）。如果没有第一阶段的处理，冒泡需要19趟排序才能完成，而经过处理后，第8趟排序就已经有序了。此时排序结束，节省了一半以上的时间。

二、代码

C++代码：

const float factor = 1.3;

template<typename T>
void comb_sort(T data[], const unsigned int n) {
    unsigned int i, j, step = n;
    bool flag = true;

    if (n < 2)
        return;
    
    // 步长处理
    while ((step = (unsigned int) (step / factor)) > 1) {
        for (i = n - 1; i >= step; i--) {
            j = i - step;
            if (data[i] < data[j])
                my_swap(data[i], data[j]);
        }
    }

    // 冒泡排序
    for (i = 0; flag && i < n - 1; i++) {
        flag = false;
        for (j = 1; j < n - i; j++) {
            if (data[j] < data[j - 1]) {
                my_swap(data[j], data[j - 1]);
                flag = true;
            }
        }
    }
}

使用clion的过程中，发现每创建一个文件，系统就会自动在头部生成注释信息：

//
// Created by <username> on 2020/2/7.
//

这个是因为开启了代码模板导致的，配置在：

Settings → Editor → File and Code Templates → Includes → C File Header

直接把这个配置删掉就可以了，注意是删掉里面的内容，不要把这一栏删掉了。

参考

File and Code Templates

Turning off “created by” header when generating files in CLion

默认情况下的，通过dot命令导出的图片分辨率很低。在高分辨率的显示器下看，图片很小，放大了也很模糊。修改分辨率的办法：

digrapvh G {
    graph [dpi=300]
}

修改后的效果：

修改前的效果：

也可以在导出的时候使用-G参数来控制：

dot -T png -Gdpi=300 -o demo.png demo.dot

参考

how-do-i-set-the-resolution-when-converting-dot-files-graphviz-to-images

一、数组

digraph demo {
    n [label="{1|2|3}" shape=record]
}

效果：

如果希望数组横过来，要设置全局的rankdir属性：

digraph demo {
    rankdir=LR
    n [label="{1|2|3}" shape=record]
}

效果：

二、链表节点

digraph demo {
    rankdir=LR
    n1 [label="{<data>data|<next>}" shape=record]
    n2 [label="{<data>data|<next>}" shape=record]
    n3 [label="{<data>data|<next>nil}" shape=record]

    n1:next:0 -> n2:data [tailclip=false]
    n2:next:0 -> n3:data [tailclip=false]
}

效果：

刷root权限的方法：系统降级+KingRoot，没有可以直接通过软件就能root的办法。

降级

降级到20160314版本，要把系统双清。必须要双清，否则可能导致变砖。官方下载地址：OPPO R9（全网通）固件下载，下载最后一个rom包。

百度网盘下载地址：提取密码6yir，包含了rom和KingRoot软件。

要双清，注意提前备份好数据。如果降级失败变砖了，可以参考OPPO R9救砖教程救砖。

KingRoot

安装好软件后直接进入软件一键Root即可获取root权限。

一、subgraph语法

子图的使用方法：

subgraph cluster* {
    // xxxx    
}

子图的语法和其他语法也是一样的，一个千万要注意的地方是子图的命名必须以cluster开头。

例如：

digraph {
    subgraph cluster_0 {
        label="Subgraph A";
        a -> c;
        b -> c;
    }

    subgraph cluster_1 {
        label="Subgraph B";
        a -> f;
        f -> c;
    }
}

效果：

二、把箭头指向容器的办法

如果希望把箭头容器，而不是指向容器内部元素的话，需要使用以下两个属性：

compound=true;
// a和b分别表示箭头的头部和尾部
xx -> yy [lhead=a ltail=b]

要注意的是compound=true属性一定需要，它是全局代码段的。

例如修改上图中的a到f的线条为a到子容器B：

digraph demo {
    compound=true;
    subgraph cluster_0 {
        label="Subgraph A";
        a -> c;
    }

    subgraph cluster_1 {
        label="Subgraph B";
        f -> c;
    }

    a -> f [lhead=cluster_1];
}

效果：

起因：刷root权限，需要给系统降级，结果降级失败，变砖了。无奈救砖。

工具：百度网盘下载，提取码b7s4，先下载救砖工具，解压到本地。压缩包有两个目录，一个是驱动，一个是恢复包，先安装驱动，然后打开恢复包里面的刷机工具。

注意，恢复数据会双清！！

恢复过程：

1. 打开恢复工具，点击Start all，此时拔掉数据线。
2. 手机关机，按住音量上键，插入数据线，开机。

如果操作没有问题，恢复工具会自动识别并开始恢复数据，第一个进度条就是恢复进度：

恢复大概需要十分钟左右，等到状态变成Cksm OK时，恢复就完成了，重启手机就行了：