代码随想录算法训练营第十四天 | leetcode：平衡二叉树,二叉树的所有路径,左叶子之和

_zzh 的个人博客 / 25 / 0 / 创建于 1个月前 / 更新于 1个月前

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;
    }
}