今日学习
找树左下角的值
题目链接/文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html
第一想法
这道题明显迭代法更简单，模板题，直接秒
/**
* 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 findBottomLeftValue = function (root) {
let res
let queue = []
queue.push(root)
while (queue.length) {
let length = queue.length
for (let i = 0; i < length; i++) {
let node = queue.shift()
if(i == 0){
res = node.val
}
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
}
return res
};
112. 路径总和
题目链接/文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
第一想法
迭代法有点像配套设施，要记录当前的数值和当前的node
/**
* 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
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function (root, targetSum) {
if(root === null) return false;
let valArr = [0]
let nodeArr = [root]
while (nodeArr.length) {
let curNode = nodeArr.shift()
let curVal = valArr.shift()
curVal += curNode.val
if (!curNode.left && !curNode.right && curVal === targetSum) {
return true
}
if (curNode.left) {
nodeArr.push(curNode.left);
valArr.push(curVal);
}
// 右节点，将当前的数值也对应记录下来
if (curNode.right) {
nodeArr.push(curNode.right);
valArr.push(curVal);
}
}
return false;
};
106.从中序与后序遍历序列构造二叉树
第一想法
递归法，其实就是用后序遍历获得中间节点的值来分割中序遍历
var buildTree = function(inorder, postorder) {
if (!inorder.length) return null;
const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
const root = new TreeNode(rootVal); // 创建中间节点
root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
return root;
}
