二叉树与递归 - 深入理解
| 题目 | 代码 | 备注 |
|---|---|---|
| 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;
};112.路径总和
- 递的时候，形参带进去了targetSum改完后的实际值，
- 也就是每条路径上每个新建的函数调用栈的targetSum值都是不一样的
- 思路：到达叶子节点的时候进行判断是否为0，那如果是多个路径，return判断是同事进行return吗？不会有先后吗？
- 归的时候看成，往root节点冒泡，传递 true/false，但是最终怎么确定？？是有true就true吗？全false就false？
js
var hasPathSum = function(root, targetSum) {
//思路：路径的话，通过递进的时候形成；每次递进减去值；判断答案，归的时候传递true/false
//节点校验
if(!root) return false;
//减去值
targetSum -= root.val;
//判断叶子节点和答案
if(root.left===null && root.right === null){
return targetSum === 0;
}
//值传递
return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
};