go并发之路(六)——实例：比较二叉查找树是否等价

发表于

本文同时参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

题意分析

  • 需要实现一个walk函数
1
2
go复制代码// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int)
  • 需要利用之前生成的walk函数实现一个same函数，来验证两个二叉树是否等价

思路分析

我们已知的其实只有二叉查找树一个条件，我们不妨看下二叉查找树的性质：

1
2
3
4
5
6
7
8
9
复制代码一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

对树数据结构有兴趣或者需要进一步学习的也可以移步我之前的文章:

因此二叉查找树一定没有相同的节点，并且前序遍历一定有序。

我们可以按顺序将二叉树的节点依次写入通道，再从通道中读取并写入数组中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
go复制代码  func DFS(t *tree.Tree, ch chan int){
      if t == nil {
          return
      }
      if t.Left != nil {
          DFS(t.Left, ch)
      }
      ch <- t.Value
      if t.Right != nil {
          DFS(t.Right, ch)
      }
  }

一个简单的dfs，可以按顺序读取二叉树的节点。

1
2
3
4
go复制代码func Walk(t *tree.Tree, ch chan int) {
    DFS(t,ch)
    close(ch)
}

walk函数调用dfs，遍历树的节点。

接下来从通道中读取数据，并将其放入数组中。不过想想并不需要切片，只需要for循环中去读取第二个通道就可以了

1
2
3
4
5
6
7
8
9
10
go复制代码for i :=range ch1{
  j,ok := <- ch2
  if !ok {
      return false
  }
  if i!=j {
      return false
  }
  fmt.Printf("ch1: %v - ch2: %v\n", i, j)
}

总体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
go复制代码func Same(t1, t2 *tree.Tree) bool{
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1) 
    go Walk(t2, ch2)
    for i :=range ch1{
      j,ok := <- ch2
      if !ok {
          return false
      }
      if i!=j {
          return false
      }
      fmt.Printf("ch1: %v - ch2: %v\n", i, j)
    }
    return true
}

总结

最开始的想法是通过将遍历后的树写入通道，再从通道读取并写入数组中，这其实是一个很“单线程”的想法，因为如果这是一道算法题，那自然是通过dfs写入数组再比较数组的方式来读取数据。此刻通道并没有产生任何作用，但是在后来想到了我们可以通过在读取通道时再读取另一个通道，来实现两棵树的比较。本题让笔者对通道又有了进一步的认识。

在查阅网上资料时，发现有些人用从通道读取数据，再对数据做异或的方式实现，因为这利用了二叉查找树无重复的性质，因此当异或结果为0时，两颗树必定相等。不过这其实是错的，因为题目中并没有表明树的数量，比如树A为1，2，两者异或为 01 ^ 10： 11,此时如果树B为3，则依旧会得到相等的结果。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%