P150. 二叉树的直径

https://algocasts.io/episodes/nwp8ArW7

@Michael

我把你的问题移到这个主题下。后面如果有关于某个已有视频的问题,直接点击视频播放页面的「讨论」按钮,在对应的帖子下提问即可。不用新开一个帖子哈。

原问题

回答

关于为什么参数使用大小为 1 的数组 d,在原视频 4 分 14 秒 开始有解释。文字内容如下:

首先实现一个辅助函数,用于计算树的最大深度。可以看到输入除了二叉树,还有一个 int 数组 d。d 是一个大小为 1 的数组,为的是存储二叉树直径的引用。Java 无法直接对 int 进行引用,另外也不建议把这个变量作为类成员变量,因为这会使同一实例的多次函数调用互相影响,得到错误答案。

关于这一点,在不同语言中,可以有不同的实现。比如有的语言可以直接使用引用形参,而另外一些语言可以使用元组,返回多个值。

Java 中使用大小为 1 的数组来存储某个基本类型变量的引用,这个小技巧在不少地方都可以看到。根本原因就在于 Java 在传递函数参数时,传递的是值而非引用。于是如果某个形参在函数中发生一系列的计算后,返回函数调用点,仍然需要使用这个形参值,就需要使用这个小技巧。

举个 C++ 的例子进行对比,C++ 可以直接使用 int& 对 int 值引用传参,因此就可以这么写:

  int diameterOfBinaryTreeRecursive(TreeNode* root) {
    int d = 0;
    maxDepth(root, d);
    return d;
  }

  int maxDepth(TreeNode* root, int& d) {
    if (!root) return 0;
    int left = maxDepth(root->left, d);
    int right = maxDepth(root->right, d);
    d = max(d, left + right);
    return max(left, right) + 1;
  }

谢谢。还有一个问题就是。Java中是不是,不存在静态数组。因为我查了下Java中的基本类型没有数组这个数据类型,换句话说数组在java中就是个引用类型。类比一下C。 在C中: int a[4] = {1,2,3,4}; 这个是static的。 int* b = malloc (4 * sizeof(int)); 这个是b是一个dynamic的数组。就是一个指向数组的指针。 而在Java中, int[] a = new int[4]; dynamic数组是这个样子的。 但是 如果我用一个初始赋值的写法: int[] a = {1,2,3,4}; 那这种情况是属于哪种类型的数组呢。

@Michael

是的。Java 中的数组都是存储在堆(Heap)上的,这一点和 C/C++ 不同,C/C++ 中允许在栈(Stack)上存储数组,并且一旦出了作用域,这个栈上的数组就会自动清除(失效)。而 Java 中不管你怎么写,无论是声明数组的同时初始化数组,还是先使用 new 开一个空间,后面再填充数组,效果都一样,数据都是存储在堆上的。

参考链接:
https://stackoverflow.com/questions/10953806/java-array-using-stack-space
https://people.eecs.ku.edu/~jrmiller/Courses/JavaToC++/StackAllocatedArrays.html

Go version

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func dfs(root *TreeNode, d *int) int {
    if root == nil {return 0}
    left := dfs(root.Left, d)
    right := dfs(root.Right, d)
    *d = max(*d, left + right)

    return max(left, right) + 1
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

func diameterOfBinaryTree(root *TreeNode) int {
    var d int
    dfs(root, &d)
    return d
}

没有特别多的面试经验,关于算法题的笔试中想要求证2个问题。
1.递归写法和非递归写法哪个得分会更高?
看视频时,此题递归写法甚好理解,非递归辅助栈的写法理解了10分钟。所以推测是非递归更好点?(在题目没有限制的情况下)
2.辅助空间结构的使用(java)
这道题的非递归写法借助了HashMap和Stack。如果考察的题目是堆排序,当然不能直接借用java集合包写好的堆结构。其他情况如果不是作为直接考试点,在没有题目限制的情况下都可以直接借助java提供好的类吧?

@zhizx

递归写法和非递归写法哪个得分会更高?

在笔试中且题目没有限制的情况下,我觉得应该优先写时间复杂度或空间复杂度更优的解法。至于是不是递归,其实并不是很重要只要题目没有明确要求)。在时间/空间复杂度相当的情况下,挑选你觉得好理解的那个版本写就行。

如果是在面试中,那就更好应对了。如果你觉得递归解法写起来又容易理解,代码又简洁美观,就尽管写递归解法好了。如果面试官想考察你写不写得出非递归解法,他是会明确告诉你的。

辅助数据结构的使用

是的。关键就是看问题的考察点是什么。只要不是这个问题的考察点,无论是内置的数据结构还是内置的函数,尽管用就是了。