二叉树与递归 - 深入理解
| 题目 | 代码 | 备注 |
|---|---|---|
| 104. 二叉树的最大深度 | 代码 | 两种方法 |
| 111. 二叉树的最小深度 | 代码 | *课后作业 |
| 404. 左叶子之和 | 代码 | *课后作业 |
| 112. 路径总和 | 代码 | *课后作业 |
| 129. 求根节点到叶节点数字之和 | 代码 | *课后作业 |
| 1448. 统计二叉树中好节点的数目 | 代码 | *课后作业 |
| 987. 二叉树的垂序遍历 | 代码 | *课后作业 |
题目
最大深度
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
//使用递归
//归的时候要加自己的深度？
//boudary
if(!root) return 0;
const l = maxDepth(root.left);
const r = maxDepth(root.right);
return Math.max(l,r) + 1;
};习题
111.二叉树的最小深度
js
//层序遍历
var minDepth = function (root) {
//boudary
if (!root) return 0;
//要进行判空，否则把null节点的子树也算进去了; 左边null就去右边
if (!root.left) return minDepth(root.right) + 1;
if (!root.right) return minDepth(root.left) + 1;
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};404.左叶子之和
- 如何判断一个节点是叶子
- 思路：递归，函数返回sum，递到叶子，再拿和，通过return进行传递
js
/**
* @param {TreeNode} root
* @return {number}
*/
var sumOfLeftLeaves = function (root) {
//边界条件
if (!root) return 0;
//左右两边树的左叶子
let sum = sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
let node = root.left;
//判断是左叶子，两个子节点null,最终，然后return的时候带上.val就行了
if (node && node.left === null && node.right === null) sum += node.val;
//注意这里不是.value
//通过这个sum来进行一个值传递，如果不是叶子就return0了
return sum;
};