深度优先遍历 DFS
解题思路
定义一个递归函数 dfs ，函数返回该节点为根的子树的深度（后序遍历）；
先递归调用左儿子和右儿子求得它们为根的子树的深度 max(L, R) ，则该节点为根的子树的深度即为 L+R+1;
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次； -
空间复杂度：
O(Height)，其中 Height 为二叉树的高度；- 由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度；
- 而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为
O(Height)；
代码实现
var diameterOfBinaryTree = function (root) {
let res = 0;
const dfs = (root) => {
if (root === null) return 0;
let left = dfs(root.left); // 左儿子为根的子树的深度
let right = dfs(root.right); // 右儿子为根的子树的深度
res = Math.max(res, left + right); // 更新 res
return Math.max(left, right) + 1; // 返回该节点为根的子树的深度
};
dfs(root);
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 235. 二叉搜索树的最近公共祖先
上一篇
评论
