代码随想录算法训练营第18天|二叉树

513. 找树左下角的值

最左边的结点的特性

1.只能是叶子结点，

2.必须考虑是最底层，所以要考虑树的深度

3.同样的深度考虑左子树

考虑迭代法,层序遍历

递归优点难搞的

/*** 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}*///最左边的结点的特性//1.只能是叶子结点，//2.必须考虑是最底层，所以要考虑树的深度//3.同样的深度考虑左子树//考虑迭代法,层序遍历
var findBottomLeftValue = function(root) {let q = [root], res = [];while(q.length > 0){let len = q.length;let curLevel = [];for(let i = 0; i < len; i++){let curNode = q.shift();curLevel.push(curNode.val);if(curNode.left) q.push(curNode.left);if(curNode.right) q.push(curNode.right);}res.push(curLevel);}return res[res.length - 1][0];  
};

112. 路径总和

/*** 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) return false;let res = [];dfs(root, 0, res);console.log('res:',res);console.log(res.indexOf(targetSum));return res.indexOf(targetSum) === -1 ? false : true;
}function dfs(node, sum, res){//叶子结点if(!node.left && !node.right){res.push(sum + node.val);return;}if(node.left) dfs(node.left, sum + node.val, res);if(node.right) dfs(node.right, sum + node.val, res);
}

113. 路径总和 II

/*** 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 {number[][]}*/
var pathSum = function(root, targetSum) {if(!root) return [];let res = [];dfs(root, 0, res, [], targetSum);return res;
};function dfs(node, sum, res, path, targetSum){path.push(node.val);sum += node.val;//叶子结点if(!node.left && !node.right){if(sum  === targetSum){res.push([...path]);//这里不能直接res.push(path)，因为JS中数组是直接传引用的，所以最后return的res中的那个数组，就是被修改过的path数组，这里用扩展运算符} return;}if(node.left){dfs(node.left, sum, res, path, targetSum);path.pop();} if(node.right){dfs(node.right, sum, res, path, targetSum);path.pop();} 
}

106. 从中序与后序遍历序列构造二叉树

能过，但是会超内存，之后在改进吧

/*** 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 {number[]} inorder* @param {number[]} postorder* @return {TreeNode}*/
var buildTree = function(inorder, postorder) {//中序。  左中右//后序。  左右中if(inorder.length == 0) return null;let val = postorder[postorder.length - 1];let root = new TreeNode(val);let index = inorder.indexOf(val);let leftInOrder = inorder.slice(0, index);let rightInOrder = inorder.slice(index + 1);let index2 = postorder.indexOf(leftInOrder[leftInOrder.length - 1]);let leftPostOrder = postorder.slice(0, index2 + 1);let rightPostOeder = postorder.slice(index2 + 1, postorder.length - 1);root.left = buildTree(leftInOrder, leftPostOrder);root.right = buildTree(rightInOrder, rightPostOeder);return root;
};