代码随想录算法训练营第十四天 | leetcode：平衡二叉树,二叉树的所有路径,左叶子之和
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
110. 平衡二叉树
解题方法
平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
判断每个节点的左右子树差是否大于1，需要从下往上传递状态，所以使用后续遍历。当递归中左右子树高度差的绝对值大于1时，返回-1表示当前不是平衡二叉树。因为当遍历节点为根节点的子树不为平衡二叉树，那么整个二叉树都不是平衡二叉树。
code
递归法
class Solution {
/**
* @param TreeNode $root
* @return Boolean
*/
function isBalanced($root) {
return $this->getHeight($root) == -1 ? false : true;
}
function getHeight($node){
if($node == null) return 0;
//左
$leftHeight = $this->getHeight($node->left);
if($leftHeight == -1) return -1;
//右
$rightHeight = $this->getHeight($node->right);
if($rightHeight == -1) return -1;
// print_r("nodeVal:" . $node->val."\n");
// print_r("leftHeight:".$leftHeight."\n");
// print_r("rightHeight:".$rightHeight."\n\r");
//中
if(abs($rightHeight - $leftHeight) > 1){
return -1;
}else{
//返回当前节点的高度
return 1 + max($leftHeight, $rightHeight);
}
}
}257. 二叉树的所有路径
解题方法
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
code
递归法
class Solution {
private $res = [];
/**
* @param TreeNode $root
* @return String[]
*/
function binaryTreePaths($root) {
if($root == null) return $this->res;
$route = '';
$this->treeLoop($root, $route);
return $this->res;
}
function treeLoop($cur, $route){
//要先收集路径，再判断叶子结点
$route .= $cur->val . "->";
if($cur->left == null && $cur->right == null) {
//去除最右边的"->"符号，收获路径
$this->res[] = rtrim($route,"->");
return;
}
if($cur->left != null){
$this->treeLoop($cur->left, $route);
}
if($cur->right != null){
$this->treeLoop($cur->right, $route);
}
}
}404. 左叶子之和
解题方法
只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。那么遍历节点就需要判断左孩子节点就是一个左叶子的情况，再做左叶子节点的叠加。可以得出以下三个判断条件：
- node->left != NULL //节点左孩子不为空
- node->left->left == NULL //节点左孩子的左孩子为空
- node->left->right == NULL//节点左孩子的右孩子为空
code
递归法
class Solution {
private $count = 0;
/**
* @param TreeNode $root
* @return Integer
*/
function sumOfLeftLeaves($root) {
$this->traversal($root);
return $this->count;
}
function traversal($root){
if($root == null) return;
//判断当前节点的左孩子节点不为空，并且左孩子节点的左右节点都为空，才能判断当前节点的左孩子节点是左叶子结点
if($root->left != null && $root->left->left == null && $root->left->right == null){
$this->count += $root->left->val;
}
if($root->left) $this->sumOfLeftLeaves($root->left);
if($root->right) $this->sumOfLeftLeaves($root->right);
return;
}
}层序遍历
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function sumOfLeftLeaves($root) {
$res = 0;
if($root == null) return $res;
$queue = new SplQueue();
$queue->enqueue($root);
while(!$queue->isEmpty()){
$count = $queue->count();
while($count--){
$node = $queue->dequeue();
if($node->left != null){
//print_r($node->left->val);
//需要判断是否叶子节点 再做叠加
if($node->left->left == null && $node->left->right == null){
$res += $node->left->val;
}
$queue->enqueue($node->left);
}
if($node->right != null){
$queue->enqueue($node->right);
}
}
}
return $res;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号