Binary Tree based Recursion & Divide Conquer 二叉树递归与分治

226. Invert Binary Tree (Easy)

Invert a binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13

Example:
Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

递归1:

1
2
3
4
5
6
7
8

class Solution:
    def invertTree(self, root):
        if not root:
            return
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

递归2：

1
2
3
4
5
6
7
8

class Solution:
    def invertTree(self, root):
        if not root:
            return
        l = self.invertTree(root.left)
        r = self.invertTree(root.right)
        root.left, root.right = r, l
        return root

递归3：

1
2
3
4
5
6

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def invertTree(self, root):
        if not root:
            return
        stack = [root]
        while stack:
            cur = stack.pop(-1)
            cur.left, cur.right = cur.right, cur.left
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return root

100. Same Tree (Easy)

Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Example 1:
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]
Output: true

Example 2:
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]
Output: false

Example 3:
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]
Output: false

递归：

1
2
3
4
5
6
7

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if (p and not q) or (q and not p) or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        stack = [(p, q)]
        while stack:
            p, q = stack.pop(-1)
            if not p and not q:
                continue
            if (p and not q) or (q and not p) or p.val != q.val:
                return False
            stack.append((p.left, q.left))
            stack.append((p.right, q.right))
        return True

五刷：高频

101. Symmetric Tree (Easy)

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

1
2
3
4
5
6
7
8
9
10
11
12

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

递归

1
2
3
4
5
6
7
8
9

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def helper(l, r):
            if not l and not r:
                return True
            if (l and not r) or (not l and r):
                return False
            return l.val == r.val and helper(l.left, r.right) and helper(l.right, r.left)
        return helper(root.left, root.right)

遍历1：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        q = deque([(root.left, root.right)])
        while q:
            l, r = q.popleft()
            if not l and not r:
                continue
            if l and not r or not l and r or l.val != r.val:
                return False
            q.append((l.left, r.right))
            q.append((l.right, r.left))
        return True

遍历2:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        s = [(root.left, root.right)]
        while s:
            l, r = s.pop()
            if (l and not r) or (r and not l):
                return False
            if (l and r) and (l.val != r.val):
                return False
            if l:
                s.append((l.left, r.right))
                s.append((l.right, r.left))
        return True

8刷：高频

##前言

这次五一出行非常不易。 大家平时很忙， 没空做功课， 一路上状况（坑）也很多。
首先，五一出行就很贵。 有人的护照在元旦去泰国以后就过期了。 一直到出发前个把月才办到新护照。 订机票需要输入护照号， 拿到新护照才知道护照号。等到出发前三周左右拿到新办好的护照，机票已经没有太多选择了。 我们在去哪网买了一个往返价格￥2873 从韩国转机的红眼航班，毕竟五一，有这个价格已经是较便宜的了。但是，这里埋下出发前的巨大一个坑，随后会介绍。 由于我们没有做功课， 不是很确定要住哪里。 直到出发前两周不到才订了第一晚的酒店：Hotel Brighton City Osaka Kitahama。 住下来这家酒店性价比还是不错。后来听说京都比较好玩就在出发前三天订了三天京都的酒店。 Hotel MyStays Kyoto-Shijo。

行程

4 月 28

4 月 29

4 月 30

5 月 1

5 月 2

5 月 3

大阪吃吃吃， 买买买。然后回北京~

住

Hotel Brighton City Osaka Kitahama 退房

####吃

大和屋，大丸百货 13 楼，地铁心斋桥站

####详细

上午睡了个懒觉，收拾好退房以后英明决定带着行李去心斋桥，行李寄存地铁，然后在心斋桥逛街。结果 700 日元的最大号柜子被人占了，只好租 500 日元第二大的柜子，发挥智慧硬塞了两个登机箱进去。

出站后觉得应该先吃午饭，在点评上看中了家餐馆叫銀や， 结果跑到门口看到贴纸说五一长假不开/(ㄒoㄒ)/~~。 后来又看到一家大和屋，在大丸百货的 13 层。 这时才发现我们的箱子其实是存在地铁四ツ橋站了。。。心斋桥和四ツ橋站在地下有通道是通的。。。

大丸百货都是高级牌子， 大和屋门口站的是和服服务员， 门口装修讲究， 差点没敢进去。 但是想想既然来了， 吃吧😝。 两人含税约人民币￥810.6

第一道是海胆，鲍鱼刺身

后面几道就不一一报菜名了（其实有些可能也说不上来）直接上图吧：

以太坊 V 神在一个采访中说过， 世界上现在分成两种人， 一种是知道什么是比特币的， 一种是不知道的。 对于知道什么是比特币的人， 解释以太坊是什么要相对容易一些。 就是比特币基础上再加了一个智能合约。 对于不知道什么是比特币的， 可以先在网上科普一下。

最近几天把 hackernoon 上面的一篇以太坊智能合约开发指南教程跑了一遍。 开发的例子灵感是来自于一部电影时间规划局。 一部褒贬不一的电影， 但是我挺喜欢的， 题材不错。 就是未来世界，钱就是时间。 所有人的身体都可以定格在 25 岁， 能活多久取决于左手上的计时器。 穷人就得每天打工赚取活下去的时间， 富人就有很多时间 / 钱。

说回智能合约， 这个智能合约就是很简单的比大小。 两个玩家， 在任何一轮玩家一号打入智能合约的钱是玩家二号打入的两倍或以上的话， 游戏结束，合约里所有的钱就归玩家一号。 反之亦然。 如两倍以内， 则进入下一轮。 每轮双方只能打一次钱进入合约。

我比较喜欢这个教程的第一点是， 一上来不要求装一大堆框架和 SDK，折腾半天也没开始开发。 简单粗暴， 先来智能合约代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

pragma solidity ^0.4.18;

contract Wrestling {
  address public playerA;
  address public playerB;

  bool public playerAPlayed;
  bool public playerBPlayed;

  uint private playerADeposit;
  uint private playerBDeposit;

  bool public gameOver;
  address public theWinner;
  uint public prize;

  constructor() public {
    playerA = msg.sender;
  }

  function registerAnOpponent() public {
    require(playerB == address(0));
    playerB = msg.sender;
  }

  function wrestle() public payable {
    require(!gameOver && (msg.sender == playerA || msg.sender == playerB));

    if (msg.sender == playerA) {
      require(!playerAPlayed);
      playerAPlayed = true;
      playerADeposit = playerADeposit + msg.value;
    } else {
      require(!playerBPlayed);
      playerBPlayed = true;
      playerBDeposit = playerBDeposit + msg.value;
    }

    if (playerAPlayed && playerBPlayed) {
      if (playerADeposit > 2 * playerBDeposit) {
        endGame(playerA);
      } else if (playerBDeposit > 2 * playerADeposit) {
        endGame(playerB);
      } else {
        endRound();
      }
    }
  }

  function endGame(address winner) internal {
    gameOver = true;
    theWinner = winner;
    prize = playerADeposit + playerBDeposit;
  }

  function endRound() internal {
    playerAPlayed = false;
    playerBPlayed = false;
  }

}

第一行 pragma solidity ^0.4.18; 是给编译器看的， 意思是用 0.4.18 版本以上的 solidity 编译器， 基本可以忽略。 后面的智能合约，如有任何现代语言的编程基础的话还是比较好懂的。 谁通过创造器（constructor）创造了合约谁就是一号玩家 playerA， playerA 和 playerB 的类型都是 address，根据 solidity 的官方文档，address 是一个 20 个字节放以太坊地址的类型。

合约创造以后，二号玩家可以调用 registerAnOpponent() 来注册。 require(playerB == address(0)); 的意思是要求二号玩家还没有被注册过（地址为 0）。合约的主体是 wrestle()，payable 的意思是这个方法可以接受付款。 后面的代码就是实现上面说的游戏的逻辑。 语法和现代语言 （java，javascript，python）基本没有什么区别。

至此， 智能合约的开发第一步就完成了， 神奇吧。 你可以把以上的代码复制粘贴到 solidity 的 IDE 中：http://remix.ethereum.org/。然后点击 start to compile，一切顺利的话，你能看到 Wrestling 是绿色的， 表示编译没问题。如下图所示：

到这里其实合约还有一个问题。 就是如果赢了的话，奖金如何取出来？我们需要加一个取钱的方法：

引言

刚要提笔却又觉得无从说起。 还是用我擅长的流水账手法吧。 从很多年前大学甚至高中开始就想有自己的个人主页。 事实是这些年确实都有。 但是由于很多原因没有坚持写。 我爸一直鼓励我多写。 而基于多年的学校教育和我对自身学习方法的认知， 如果我不记笔记， 知识就没有内化，没有充分理解。 写到这里，我想起了大学毕业的一个小遗憾。 当时从比利时搬家回上海， 为了轻车简从，把大学期间打印的讲义和笔记都扔掉了， 堆砌起来目测可能有将近一立方米， 可惜没有照片，现在也是口说无凭。 只能作为永远的遗憾和后辈们引以为鉴的教训了。

一直没有去写的另一个原因是， 写的东西都零散的散落在互联网的各个阴暗角落。 从 blogger 到 msn space 再到简书。互联网告诉我们，没有任何的平台是永生的。 那为什么要为了这种转瞬即逝的东西去耗费时间精力去写呢？

很惭愧，作为一个科班出身的人， 一直到最近我才开始较频繁的使用程序员神器之一 github。 发现这么些年来， 加入版本管理和云存储的东西永生的几率是最大的。 移动硬盘可能摔坏， 优盘可能丢失。

长久以来我都想把写的东西弄到版本管理里去。 直到现在才有时间去梳理这些一直想做却因为时间和借口没有做的事情。

这篇文是我用 markdown 真正意义上写的第一篇。 其实一点儿 markdown 的语法都没用到， 而我知道的也就是最基本的标题那些。然而它的意义在于， 这篇文存在 github 上，github 如果倒闭了， 我还可以转到下一个版本管理的平台上。不依赖 github 提供迁移的工具。这一点很重要， 其他的平台如 msn space 如果迁移图片的链接排版会乱的话相当于之前写的都白费了。

update: 在写这篇的时候发现 hexo 传图非常不好用， 我现在用的是本地的 markdown 编辑器 Tyora， 如果既要 Typora 里能出图， 又要 index 和点进文章里如： yourdomainname.com/2018/04/19/article-title/ 以后能出图就要依赖图床。呃😓…没想到这么多年还是没有一个彻底的解决方案。 先用图床吧。

之前有用 Jekyll 和 Octopress， 其中 octopress 的主题 greyshade 最令我满意。 截图如下：

update: 看了下 github 上 greyshade 的例子， 基本上都被 hexo 和 next 抢走了

然而， Jekyll 是 Ruby On Rails 写的， 我不熟悉 Ruby， 配置实在是搞不定。 Octopress 维护好像不是很积极了。

Hexo

最近发现基于 node.js 的 Hexo， 还有这个主题 next。基于 js 的还是比基于 Ruby 的好上手得多。 两个项目的维护好像都还比较及时。 以后可能还会换静态页面的解决方案， 但是， 文章都会一直用 github 保存下去。 我很满意。

区块链 Hackathon

最近在看区块链的机会， 6 月 9 号在北京有一个 SegmentFault 办的 hackathon， 我组了个队， 背景都是硅谷海归，还有 2-3 个参队名额。 希望有时间有兴趣的小伙伴联系我一起玩一下。