球拍：二叉树的最大高度

Question

我正在尝试在球拍中创建一个代码，它将在二叉搜索树中找到从根到叶的最大距离。

我已经看到这是用 C++ 完成的，但在将它转换为 racket 时遇到了问题。我已经设法计算出树中的所有节点，但还没有设法单独计算出任何路径。

有什么建议吗？我见过模板和所有这些，但仍然没有成功。

这是我目前尝试过的方法

 (define-struct node (left right))

 (define (maxdepth tree)
    (cond 
          [(null? tree) 0]
          [ (> (size (node-left tree)) (size (node-right tree)))
                   (maxdepth (node-left tree))]
[else (maxdepth (node-right tree))]))


  (define (size tree)
      (if (null? tree) 0
         (+ 1 (size (node-left tree)) (size (node-right tree)))))

Answer 1

我们只需要一个函数——maxdepth，只需要求出每个子树的max加上当前节点的高度：

(define (maxdepth tree)
  (cond 
    [(null? tree) 0]
    [else (+ 1 (max (maxdepth (node-left  tree))
                    (maxdepth (node-right tree))))]))

球拍：二叉树的最大高度

racket: maximum height of a binary tree

tree

height

binary-tree

racket

distance