讨论/《二叉树》 - 运用递归解决树的问题/
《二叉树》 - 运用递归解决树的问题
共 8 个回复

自顶向下

问题:给定一个二叉树,请寻找它的最大深度。
我们知道根节点的深度是1。 对于每个节点,如果我们知道某节点的深度,那我们将知道它子节点的深度。 因此,在调用递归函数的时候,将节点的深度传递为一个参数,那么所有的节点都知道它们自身的深度。

自底向上

问题:对于树的单个节点,以节点自身为根的子树的最大深度x是多少?
如果我们知道一个根节点,以其左子节点为根的最大深度为l和以其右子节点为根的最大深度为r,我们是否可以回答前面的问题? 当然可以,我们可以选择它们之间的最大值,再加上1来获得根节点所在的子树的最大深度。 那就是 x = max(l,r)+ 1

就是贴出来那个链接的【5】
当时自己还费了半天劲画了个图hh
回头看看思路大致正确嘛~

求二叉树深度这个例子实在是太棒了!
前段时间刚做过一个自底向下求深度的题但是感觉一知半解 现在明白了原理一看好清晰!

2.自底向上

每个递归层次上

  • 首先对所有子节点递归地使用调用函数
  • 然后根据返回值和根节点本身的值得到答案

所以这个过程很像是后序遍历

先深入到一个地方 再更新结果

【0】设置好递归函数(只需要输入节点即可) 函数可以直接返回答案

【1】设置特殊值退出条件

【2】对左右子树调用递归函数

【3】左子树返回一个值 右子树返回一个值 最后将两边的值进行汇总得到最终解

return specific value for null node
left_ans = bottom_up(root.left)			// call function recursively for left child
right_ans = bottom_up(root.right)		// call function recursively for right child
return answers                           // answer <-- left_ans, right_ans, root.val

求二叉树深度的例子

伪代码:

return 0 if root is null                 // return 0 for null node
left_depth = maximum_depth(root.left)
right_depth = maximum_depth(root.right)
return max(left_depth, right_depth) + 1	// return depth of the subtree rooted at root

[0]

public int maximum_depth(TreeNode root)

[1]

if (root == null){
    return 0;
}

[2]

int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);

[3]

return max(left_depth, right_depth) + 1; 

1

加油

多模拟模拟 加油!

自顶向下还是不太理解。

mark启发