2018年12月

一、拓扑图

学习linux的网络框架netfilter,想用centos作为路由器,在下面接PC产生流量测试。

默认情况下linux是没有开启数据包转发功能的,需要手动配置,linux使用centos6.9,网络拓扑图如下:

路由器的eth0口接外网,IP地址192.168.123.102,内网口eth0地址10.0.0.x/24,希望PC通过路由nat上网。

二、转发配置

开启路由转发首先检查好防火墙配置,清空原有的nat规则:

iptable -F

然后添加nat规则,一共有两种方式:

第一种:iptables -t nat -A POSTROUTING -s 10.0.0.0/24 -j SNAT --to 192.168.123.102

第二种:iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

其中的部分参数含义为:

  • -t: 类型为nat
  • -A: 添加新规则到规则链的末尾
  • POSTROUTING: 在包就要离开防火墙之前改变其源地址
  • -s: 源地址段,这里设置我的内网地址网段10.0.0.0/24
  • -j SNAT: 满足snat条件的时候跳转
  • --to: 跳转时设置的Ip地址
  • -o: 跳转时的出口设备为eth0

具体可参考防火墙规则,这里设置好后,开启设备的数据包转发:

echo 1 > /proc/sys/net/ipv4/ip_forward

然后快乐的

转发永久生效

上面的echo开启数据包转发只是临时生效,下次重启后就失效了,如果需要永久生效,得修改/etc/sysctl.conf文件,把net.ipv4.ip_forwar设置为1。

> sed -i 's#net.ipv4.ip_forward = 0#net.ipv4.ip_forward = 1#g' /etc/sysctl.conf
> grep net.ipv4.ip_forwar /etc/sysctl.conf # 确认是否修改成功了
net.ipv4.ip_forward = 1 # 已经修改好了
> sysctl -p # 生效配置
net.ipv4.ip_forward = 1 # 这里也可以看到值被修改成了1
net.ipv4.conf.default.rp_filter = 1
net.ipv4.conf.default.accept_source_route = 0
kernel.sysrq = 0
kernel.core_uses_pid = 1
net.ipv4.tcp_syncookies = 1
kernel.msgmnb = 65536
kernel.msgmax = 65536
kernel.shmmax = 68719476736
kernel.shmall = 4294967296

三、生效性测试

检测是否生效,给PC配置好IP,然后ping百度,同时设备上也开启抓包:

maqian@d2.maqian.co:~$ tcpdump -i eth1 -nnn
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth1, link-type EN10MB (Ethernet), capture size 65535 bytes
16:35:42.880920 IP 10.0.0.2.63573 > 223.5.5.5.53: 48582+ A? baidu.com. (27)
16:35:42.924100 IP 223.5.5.5.53 > 10.0.0.2.63573: 48582 2/5/5 A 220.181.57.216, A 123.125.115.110 (229)
16:35:42.938192 IP 10.0.0.2 > 220.181.57.216: ICMP echo request, id 1, seq 11, length 40
16:35:43.021923 IP 220.181.57.216 > 10.0.0.2: ICMP echo reply, id 1, seq 11, length 40
16:35:43.947976 IP 10.0.0.2 > 220.181.57.216: ICMP echo request, id 1, seq 12, length 40
16:35:44.028291 IP 220.181.57.216 > 10.0.0.2: ICMP echo reply, id 1, seq 12, length 40
16:35:44.963608 IP 10.0.0.2 > 220.181.57.216: ICMP echo request, id 1, seq 13, length 40
16:35:45.043968 IP 220.181.57.216 > 10.0.0.2: ICMP echo reply, id 1, seq 13, length 40
16:35:45.979290 IP 10.0.0.2 > 220.181.57.216: ICMP echo request, id 1, seq 14, length 40
16:35:46.058447 IP 220.181.57.216 > 10.0.0.2: ICMP echo reply, id 1, seq 14, length 40
16:35:47.923349 ARP, Request who-has 10.0.0.2 tell 10.0.0.1, length 28
16:35:47.923695 ARP, Reply 10.0.0.2 is-at 00:0c:29:60:22:cc, length 46

区别:

  1. 指针是一个变量类型,引用只是一个变量别名。
  2. 指针可以不用初始化,引用必须初始化。
  3. 指针可以指向空地址,引用不能指向空。
  4. 指针初始化后可以修改,引用不能修改。

其他:

  • 引用本质上也是一个指针,内部实现是一个常量指针。
  • C++中一般建议使用引用,不要使用指针。函数传值建议使用const引用。

 一、条件变量

条件变量是多线程的一种同步方式,它允许多个线程以无竞争的方式等待特定事件发生。无竞争的意思是,当条件满足时,条件满足这个讯号会发送给所有的监听者线程,但多个线程中只有一个能获取到特定事件。条件变量需要配合互斥量一起使用。

相关数据结构和函数:

#include <pthread.h>

// 销毁条件变量
int pthread_cond_destroy(pthread_cond_t *cond);
// 初始化条件变量
int pthread_cond_init(pthread_cond_t *restrict cond,
       const pthread_condattr_t *restrict attr);
// 初始化条件变量
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

条件变量的数据结构为pthread_cond_t,和其他同步的数据结构一样,也提供了两种方式来初始化。一种是通过赋值的方式,一种是通过函数的方式。在使用pthread_cond_init对初始化条件变量的时候,attr参数一般为NULL。

对条件变量加锁的方式:

#include <pthread.h>

// 等待条件满足
int pthread_cond_wait(pthread_cond_t *restrict cond,
       pthread_mutex_t *restrict mutex);
// 带有超时条件的等待
int pthread_cond_timedwait(pthread_cond_t *restrict cond,
       pthread_mutex_t *restrict mutex,
       const struct timespec *restrict abstime);

在对条件变量加锁的时候,需要传入一把已经处于加锁状态的互斥量,此时函数会把当前线程放到条件等待的列表上并对互斥量解锁。此时线程进入条件等待状态,当有信号到达时便会触发。

通知条件满足的函数:

#include <pthread.h>
int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);

pthread_cond_signal函数会唤醒条件等待队列上的至少一个线程,pthread_cond_broadcast会唤醒条件队列上的所有线程。

条件队列一般用于消息队列,用于统一、协调多个生产者和消费者之间的竞争关系。

二、使用示例

以下使用了三个线程作为消费者,分别从全局队列上获取消息消费:

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include "log.h"

#define THREAD_COUNT 3

// 消息结构
struct msg_st {
    unsigned int msg_id;
    struct msg_st *next;
};

static struct msg_st *msg_queue = NULL;
static pthread_cond_t g_cond = PTHREAD_COND_INITIALIZER;
static pthread_mutex_t g_mutex = PTHREAD_MUTEX_INITIALIZER;

// 消费线程函数
void *handle_msg(void *arg) {
    struct msg_st *msg;
    while (1) {
        pthread_mutex_lock(&g_mutex);
        while (msg_queue == NULL) {
            pthread_cond_wait(&g_cond, &g_mutex);
        }

        // 提取消息
        msg = msg_queue;
        msg_queue = msg_queue->next;
        pthread_mutex_unlock(&g_mutex);

        // 退出
        if (msg->msg_id == (unsigned int) -1) {
            info("Thread 0x%x exit!", (unsigned int) pthread_self());
            break;
        }

        info("Thread 0x%x: msg_id = %u", (unsigned int) pthread_self(), msg->msg_id);
    }
    return NULL;
}

// 生产消息函数
void create_msg(struct msg_st *msg) {
    pthread_mutex_lock(&g_mutex);
    msg->next = msg_queue;
    msg_queue = msg;
    pthread_mutex_unlock(&g_mutex);
    pthread_cond_signal(&g_cond);
}

int main() {
    int i;
    struct msg_st msg[10];
    pthread_t pid[THREAD_COUNT];

    debug("start create threads");
    // 创建3个线程作为消费者
    for (i = 0; i < 3; i++) {
        pthread_create(&pid[i], NULL, handle_msg, NULL);
    }

    debug("start create msgs");
    // 生产10个消息
    for (i = 0; i < 10; i++) {
        msg[i].msg_id = i + 1;
        msg[i].next = NULL;
        create_msg(&msg[i]);
    }

    // 休眠1秒,确保所有消息都被消费者消费完成
    sleep(1);

    // 退出所有线程
    debug("start create exit msgs");
    for (i = 0; i < THREAD_COUNT; i++) {
        msg[i].msg_id = (unsigned int) -1;
        msg[i].next = NULL;
        create_msg(&msg[i]);
    }

    // 回收所有线程
    debug("start join threads");
    for (i = 0; i < THREAD_COUNT; i++) {
        pthread_join(pid[i], NULL);
    }

    debug("program end");

    return 0;
}

运行结果,10个消息分别被3个线程打印出来了:

三、其他

3.1 “惊群”效应

条件变量是否存在惊群效应呢?

不会,线程执行wait操作的时候会被放到一个条件等待队列里面去。当条件满足的时候,系统会自动选择队列前面的线程来消费队列。

3.2 为什么wait前要加锁,这样不会死锁吗?

不会,执行wait操作时需要的是一把已经加锁的互斥量,这个锁在wait函数中会解开。

这样做的目的:如果在wait前没有加锁,生产者线程产生了一个消息并发送信号,再执行wait后信号就丢失了。

3.3 生产者的信号为什么放在unlock之后?

wait收到信号之后要对互斥量加锁,此时锁还被生产者持有,消费者依旧还要等待锁的释放,才能持有锁。对消费者而言,最理想的情况就是生产者产生消息后,我立马就能读取消息,此时的互斥量是用来和其他消费者线程同步的,而不是和生产者线程同步。

一、Let's Encrypt

Let's Encrypt SSL证书是一个免费的公益项目,由Mozilla、Cisco、Akamai、IdenTrust、EFF等组织人员发起,主要的目是为了推进网站从HTTP向HTTPS过度的进程,目前已经有越来越多的商家加入和赞助支持。

使用Let's Encrypt生成域名证书的前置条件:

  1. 拥有域名,能自主配置DNS记录。或者提供web服务器验证,需要在网站目录下放一个文件,推荐第一种方式。
  2. 获取证书的环境要能访问到DNS服务器,因为中途需要校验DNS解析。
  3. 拥有主机的超级权限,中途需要更新和安装组件。

二、申请流程

第一步:拉代码,代码开源于Github

> git clone https://github.com/letsencrypt/letsencrypt
Cloning into 'letsencrypt'...
remote: Enumerating objects: 29, done.
remote: Counting objects: 100% (29/29), done.
remote: Compressing objects: 100% (27/27), done.
remote: Total 61424 (delta 7), reused 4 (delta 2), pack-reused 61395
Receiving objects: 100% (61424/61424), 20.12 MiB | 5.01 MiB/s, done.
Resolving deltas: 100% (44625/44625), done.

完成后执行命令生成证书:

> ./certbot-auto certonly -d *.maqian.art --manual \
>     --preferred-challenges dns \
>     --server https://acme-v02.api.letsencrypt.org/directory

解释一下各个参数的含义:

  • certonly: 表示当前为安装模式
  • --manual: 表示手动安装插件,不要自动安装了
  • --preferred-challenges dns: 校验方式为dns验证
  • -d *.maqian.art: 要生成的域名列表,可以为多个,如果是多个分别以-d加上即可
  • --server: Let's Encrypt ACME v2版本使用的服务器

接下来的步骤一直接受即可,直到出现添加DNS记录为止:

Requesting to rerun ./certbot-auto with root privileges...
[sudo] password for ma: 
Saving debug log to /var/log/letsencrypt/letsencrypt.log
Plugins selected: Authenticator manual, Installer None
Enter email address (used for urgent renewal and security notices) (Enter 'c' to
cancel): maqian@dyxmq.cn

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Please read the Terms of Service at
https://letsencrypt.org/documents/LE-SA-v1.2-November-15-2017.pdf. You must
agree in order to register with the ACME server at
https://acme-v02.api.letsencrypt.org/directory
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(A)gree/(C)ancel: A

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Would you be willing to share your email address with the Electronic Frontier
Foundation, a founding partner of the Let's Encrypt project and the non-profit
organization that develops Certbot? We'd like to send you email about our work
encrypting the web, EFF news, campaigns, and ways to support digital freedom.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(Y)es/(N)o: Y
Obtaining a new certificate
Performing the following challenges:
dns-01 challenge for sinfor.maqian.io

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
NOTE: The IP of this machine will be publicly logged as having requested this
certificate. If you're running certbot in manual mode on a machine that is not
your server, please ensure you're okay with that.

Are you OK with your IP being logged?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(Y)es/(N)o: Y

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Please deploy a DNS TXT record under the name
_acme-challenge.maqian.art with the following value:

zw1MeEkmGZOqSqiySp9Ke8S5a9BXC3O4tYzlbjwU-CU

Before continuing, verify the record is deployed.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Press Enter to Continue

此时需要在DNS服务商处添加dns解析,记录类型为TXT,记录为_acme-challenge,值为zw1MeEkmGZOqSqiySp9Ke8S5a9BXC3O4tYzlbjwU-CU。当DNS记录设置好后,新开一个终端查询解析是否生效:

> nslookup -type=txt _acme-challenge.maqian.art
Server:        100.100.2.136
Address:    100.100.2.136#53

Non-authoritative answer:
_acme-challenge.maqian.art    text = "zw1MeEkmGZOqSqiySp9Ke8S5a9BXC3O4tYzlbjwU-CU"

Authoritative answers can be found from:

当查询到的记录和给定的都一致之后按下任意键执行下一步,如果DNS验证成功就会出现以下信息:

Waiting for verification...
Cleaning up challenges

IMPORTANT NOTES:
 - Congratulations! Your certificate and chain have been saved at:
   /etc/letsencrypt/live/maqian.art-0001/fullchain.pem
   Your key file has been saved at:
   /etc/letsencrypt/live/maqian.art-0001/privkey.pem
   Your cert will expire on 2019-03-22. To obtain a new or tweaked
   version of this certificate in the future, simply run certbot-auto
   again. To non-interactively renew *all* of your certificates, run
   "certbot-auto renew"
 - If you like Certbot, please consider supporting our work by:

   Donating to ISRG / Let's Encrypt:   https://letsencrypt.org/donate
   Donating to EFF:                    https://eff.org/donate-le

此时就表示证书已经申请完成了,存放的路径为:/etc/letsencrypt/live/maqian.art-0001。

> sudo ls /etc/letsencrypt/live/maqian.art-0001/ -l
total 4
lrwxrwxrwx 1 root root  39 Dec 22 23:46 cert.pem -> ../../archive/maqian.art-0001/cert1.pem
lrwxrwxrwx 1 root root  40 Dec 22 23:46 chain.pem -> ../../archive/maqian.art-0001/chain1.pem
lrwxrwxrwx 1 root root  44 Dec 22 23:46 fullchain.pem -> ../../archive/maqian.art-0001/fullchain1.pem
lrwxrwxrwx 1 root root  42 Dec 22 23:46 privkey.pem -> ../../archive/maqian.art-0001/privkey1.pem
-rw-r--r-- 1 root root 692 Dec 22 23:46 README

三、安装到nginx

上面一共生成了四个文件,各自的用途为:

  • cert.pem: Apache服务器端证书
  • chain.pem: Apache根证书和中继证书
  • fullchain.pem: Nginx所需要ssl_certificate文件
  • privkey.pem: 安全证书KEY文件

部署到nginx只需要添加一下指令即可:

ssl on;
ssl_certificate /etc/letsencrypt/live/maqian.art-0001/fullchain.pem;
ssl_certificate_key /etc/letsencrypt/live/maqian.art-0001/privkey.pem;

打开网站,点开左上角地址栏的https,查看证书:

一、概述

docker默认存在/var/lib/docker目录下,一般情况下这个目录都没有单独挂载,都是放在根目录下的,目录较小。

为了避免占用太多/var目录空间,并且方便管理,可以把存储目录放到其他的文件夹,例如/data/docker。

二、步骤

创建想要修改的目录,假设是/data/docker,首先创建文件夹并赋予权限。

> mkdir /data/docker
> chgrp -R docker /data/docker

停掉docker,修改docker的systemd服务文件,位于/usr/lib/systemd/system/docker.service,修改ExecStart一行:

> systemctl restart docker
> sed -i 's#ExecStart=/usr/bin/dockerd#ExecStart=/usr/bin/dockerd --graph /data/docker#g' /usr/lib/systemd/system/docker.service

重启docker:

> systemctl daemon-reload
> systemctl start docker 

验证是否修改成功:

> docker info | grep "Root"
Docker Root Dir: /data/docker
> ll /data/docker/
total 48
drwx------ 2 root root 4096 Dec 22 22:39 builder
drwx--x--x 3 root root 4096 Dec 22 22:39 containerd
drwx------ 2 root root 4096 Dec 22 22:39 containers
drwx------ 3 root root 4096 Dec 22 22:39 image
drwxr-x--- 3 root root 4096 Dec 22 22:39 network
drwx------ 3 root root 4096 Dec 22 22:39 overlay2
drwx------ 4 root root 4096 Dec 22 22:39 plugins
drwx------ 2 root root 4096 Dec 22 22:39 runtimes
drwx------ 2 root root 4096 Dec 22 22:39 swarm
drwx------ 2 root root 4096 Dec 22 22:39 tmp
drwx------ 2 root root 4096 Dec 22 22:39 trust
drwx------ 2 root root 4096 Dec 22 22:39 volumes

来源:力扣(LeetCode)

链接:113. 路径总和 II

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

一、题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明:叶子节点是指没有子节点的节点。

示例:

给定如下二叉树,以及目标和 sum = 22:

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

二、题解

说明:

此题是112. 路径总和Ⅰ的升级版(题解参考:),相对于第一题来说,有以下两点不通:

  1. 题Ⅰ只需要判断存在即可,该题需要找到所有可能的结果。
  2. 找到所有结果的同时,该题还需要保存所有的路径。

算法:

递归+深搜遍历所有的树节点,每遍历一个节点除了计算sum是否满足条件以外,还要记录下该节点。当遇到满足条件的叶节点,把当前路径加到结果中去。需要利用到两个辅助的数组。

代码:

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return m_ans;
    }
private:
    void dfs(TreeNode *root, int sum) {
        if(root == NULL) {
            return;
        }

        // 节点添加到临时的数组里面去
        m_vec.push_back(root->val);
        sum -= root->val;

        if (root->left == NULL && root->right == NULL && sum == 0) {
            // 当前临时数组加入到结果数组中
            m_ans.push_back(m_vec);
        }

        // 遍历左节点
        if (root->left) {
            dfs(root->left, sum);
        }
        
        // 遍历右节点
        if (root->right) {
            dfs(root->right, sum);
        }
        
        // 最关键的一步:回溯状态
        // 函数入口处把当前节点添加到临时数组里面去了,这里退出的时候要删掉这一个节点
        // 避免当前节点还存在于临时数组中,影响后续的遍历结果
        m_vec.pop_back();
    }

    vector<vector<int>> m_ans; // 保存所有的结果
    vector<int> m_vec; // 临时保存路径的数组
};

复杂度分析:

  • 时间复杂度:访问每个节点一次,时间复杂度为O(N) ,其中N是节点个数。
  • 空间复杂度:需要用到两个数组,其中一个是保存结果的数组可不算入空间占用,另外一个保存路径的临时数组最坏情况下(树是一条线,即类似链表的时候)占用O(N) ,平均和最优情况下(树是平衡树)占用O(log(N))。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/maximum-subarray/

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

一、题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

  • 输入:[-2,1,-3,4,-1,2,1,-5,4]
  • 输出:6
  • 解释:连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

分治法并不能算是最优解,但是可以锻炼对该算法的掌握情况。本题不考虑此算法。

二、题解

2.1 贪心算法

算法:

  1. 遍历数组,使用sum变量计算每一个节点时的最大和,用ans表示当前所有区间的最大子序和。
  2. 运行到第i个节点的时候,如果sum > 0,说明对当前节点有增益效果,sum继续加上当前节点。
  3. 如果sum <= 0,说明之前的序列对当前节点来说没有增益效果,之前的和可以舍弃。sum从当前节点开始重新计算。
  4. 然后比较ans和sum的大小,较大的赋值给sum。

图例:

图片来源于解答:画解算法:53. 最大子序和 , © 著作权归作者所有 。

以数组[-2, 3, -1, 1, -3]为例,初始化时设置sum为0,ans为第一个元素的值:

访问第一个元素-2,当前sum为0,更新sum为当前节点的值-2,sum和ans对比ans还是-2:

image2781361f9b1cc7d6.png

访问第二个元素3,因为sum = -2,如果加上当前节点,会使得连续和变成1(还不如不加,不加是3)。因此重新计算sum,设置sum为当前节点值3,继续往前计算:

imagefd03c8e73879b133.png

访问第三个元素-1,此时sum > 0,对-1有增益效果,sum加上-1等于2,ans不变:

image1f06514c3fa63f36.png

第四个元素:

image8742e9aae039ff80.png

到第五个元素时,sum = 3,加上-3之后等于0,ans依旧等于3:

imagedaf7eae811ef6e59.png

然后到此结束,最大连续和是3。

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans, sum, i;
        ans = nums.size() > 0 ? nums[0] : 0;

        for (i = 0, sum = 0; i < nums.size(); i++) {
            if (sum <= 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }

            ans = max(ans, sum);
        }
        return ans;
    }
};

image.png

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

2.2 动态规划

算法:

其实动态规划的思路和上面的贪心算法差不多,关键的结果是动态规划的状态方程:假设dp[i]是第i个节点时候的最大连续和,那怎么计算它的值呢?

其实还是和上面的贪心算法一样,只要dp[i - 1]加上当前节点的和大于当前节点,那么dp[i]就等于和值。否则dp[i]就应该设置为当前节点值,所以它的状态转移方程是:

dp[0] = nums[0];
dp[i] = max(dp[i - 1] + nums[i], nums[i])

代码:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i, sum;
        vector<int> dp(nums.size());

        if (nums.size() == 0) {
            return 0;
        }

        dp[0] = nums[0];
        sum = dp[0];

        for (i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            sum = max(dp[i], sum);
        }

        return sum;
    }
};

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n),整个状态中只用到了dp[i]和dp[i - 1],优化成O(1)。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/diameter-of-binary-tree

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

一、题目描述

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意:两结点之间的路径长度是以它们之间边的数目表示。

二、题解

本题最重要的一个点是要理清题意,求的是最大直径,是树内任意两点间的距离的最大值,不是求根节点到任意节点间距离的最大值(即深度)。

想法:

任意一条路径可以被写成两个箭头(不同方向),每个箭头代表一条从某些点向下遍历到孩子节点的路径。

假设我们知道对于每个节点最长箭头距离分别为L,R,那么最优路径经过L + R + 1个节点。

算法:

按照常用方法计算一个节点的深度:max(depth of node.left, depth of node.right) + 1。在计算的同时,经过这个节点的路径长度为1 + (depth of node.left) + (depth of node.right)。搜索每个节点并记录这些路径经过的点数最大值,期望长度是结果-1

/**
 * 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:
    int diameterOfBinaryTree(TreeNode* root) {
        unsigned int diameter = 1;
        depth(root, diameter);
        return diameter - 1;
    }
private:
    int depth(TreeNode *node, unsigned int &diameter) {
        unsigned int lDepth, rDepth;
        if (node == NULL) {
            return 0;
        }
        lDepth = depth(node->left, diameter);
        rDepth = depth(node->right, diameter);

        diameter = max(diameter, lDepth + rDepth + 1);

        return max(lDepth, rDepth) + 1;
    }
};

复杂度分析:

  • 时间复杂度:O(N),每个节点只访问一次。
  • 空间复杂度:O(N),深度优先搜索的栈开销。

2020-03-10添加

为了完成leetcode每日1题打卡计划,使用golang重新提交了一次。

计算深度和直径的方式和上面略有不同,原理还是一样的:

func depth(root *TreeNode, diameter *int) int {
    if root == nil {
        return 0
    }

    // 左子节点的深度
    lDepth := depth(root.Left, diameter) + 1
    // 右子节点的深度
    rDepth := depth(root.Right, diameter) + 1

    // 当前节点的直径
    curDiameter := lDepth + rDepth - 1
    // 更新最大的直径
    if *diameter < curDiameter {
        *diameter = curDiameter
    }

    // 返回最大深度
    if lDepth < rDepth {
        return rDepth
    } else {
        return lDepth
    }
}

func diameterOfBinaryTree(root *TreeNode) int {
    var diameter int
    diameter = 0
    depth(root, &diameter)
    return diameter
}