二叉树系列 0
前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点
对节点的访问顺序其实是一样的,但是输出顺序不一样
如果能遍历一遍得到结果的,就可以用遍历法。而如果涉及子树结果的(可分解为子问题),就可以用递归的方法。
后序位置才能通过返回值获取子树的信息。一旦发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了。
二叉树的最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
递归
| func maxDepth(root *TreeNode) int { if root == nil { return 0 } return 1 + max(maxDepth(root.Left), maxDepth(root.Right)) }
func max(a, b int) int { if a > b { return a } return b }
|
遍历
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
| int res = 0;
int depth = 0;
int maxDepth(TreeNode root) { traverse(root); return res; }
void traverse(TreeNode root) { if (root == null) { res = Math.max(res, depth); return; } depth++; traverse(root.left); traverse(root.right); depth--; }
|
二叉树的直径
https://leetcode-cn.com/problems/diameter-of-binary-tree/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| var maxDiameter int
func diameterOfBinaryTree(root *TreeNode) int { maxDiameter = 0 maxDepth(root) return maxDiameter }
func maxDepth(root *TreeNode) int { if root == nil { return 0 } maxLeft, maxRight := maxDepth(root.Left), maxDepth(root.Right) myDiameter := maxLeft + maxRight maxDiameter = max(maxDiameter, myDiameter) return 1 + max(maxLeft, maxRight) }
func max(a, b int) int { if a > b { return a } return b }
|