代码随想录算法训练营第17天|二叉树
平衡二叉树
这种开销太大了,最好是能够在获得子树高的递归中同时判断子树是否平衡,但是我纠结的是递归的输出是布尔类型,而不是数字类型,怎么在迭代子树是否平衡时计算子树的高度呢(迭代可以计算,但是我想不通的是怎么返回)
/**
* 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 {boolean}
*/
// 1.输入参数:结点
// 输出:以该结点为根节点的子树是否是平衡的
// 2.递归边界,结点为空
// 3.单层逻辑分析:
// 了解平衡二叉树:平衡二叉树的左右子树的高的差值不会超过1
// 所以在只要求左子树和右子树的高度并进行判断
var isBalanced = function(root) {
if(!root) return true;
//判断左右子树是否是平衡二叉树
let flag = isBalanced(root.left) && isBalanced(root.right);
if(!flag) return false;
//左右子树是平衡二叉树,判断以root为根的二叉树是否平衡
let ldepth = gethigh(root.left);
let rdepth = gethigh(root.right);
console.log(ldepth,rdepth);
if(Math.abs(ldepth - rdepth) > 1) return false;
return true;
};
function gethigh(root){
if(!root) return 0;
return 1 + Math.max(gethigh(root.left), gethigh(root.right));
}
参考了代码随想录,解决办法就是改变函数的输出,把迭代函数主体看作是计算子树高度的迭代,并在计算时顺便判断子树是否平衡,如果不平衡的话直接输出-1,平衡就正常输出子树的高数
/**
* 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 {boolean}
*/
var isBalanced = function(root) {
return getHeight(root) === -1 ? false :true;
};
function getHeight(node){
if(!node) return 0;
let leftHeight = getHeight(node.left);
if(leftHeight === -1) return -1;
let rightHeight = getHeight(node.right);
if(rightHeight === -1) return -1;
if(Math.abs(leftHeight - rightHeight) > 1) return -1;
return 1 + Math.max(leftHeight, rightHeight);
}
树的路径
/**
* 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 {string[]}
*/
var binaryTreePaths = function(root) {
let res = [];
dfs(root, res, "")
return res;
};
function dfs(node, res, str){
str += node.val;
if(!node.right && !node.left){//在这里判断是否是叶子结点,可以提前在为null前回溯
res.push(str);
return;
}
if(node.left) dfs(node.left, res, str + "->");
if(node.right) dfs(node.right, res, str + "->");
}
404. 左叶子之和
/**
* 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 sumOfLeftLeaves = function(root) {
let res = [];
if(root.left || root.right) dfs(root, res);
let sum = 0;
console.log('sum:',res);
for(item of res){
sum += item;
}
return sum;
};
function dfs(node, res){
// 叶子结点
if(!node.left && !node.right){
console.log(node.val);
res.push(node.val)
return;
}
// 非叶子结点
let leftChild = node.left;
let rightChild = node.right;
// 如果有左孩子,都走
if(leftChild) dfs(leftChild, res);
// 如果有右孩子,判断右孩子是不是叶子结点
if(rightChild){
if(!rightChild.left && !rightChild.right){
return;
}else{
// 不是叶子结点,走
dfs(rightChild, res);
}
}
}
// 该结点是叶子结点,必须是右叶子
// 该结点不是叶子结点,那向哪个方向遍历
// 如果左孩子是叶子结点,走
//如果左孩子不是叶子结点,走
//如果右孩子是叶子结点,不走
//如果右孩子不是叶子结点,走
//综上,只需要判断右孩子是不是叶子结点