代码随想录算法训练营第十五天 | leetcode：找树左下角的值 ,路径总和,构造二叉树

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

513. 找树左下角的值

解题方法

本题要找出树的最后一行（最底层）的最左边的值。涉及到层数（行数）的问题，用层序遍历非常简单。只需要用层序遍历所有节点，取最底层的第一个元素即可。
使用递归误区：用递归的话就就一直向左遍历，最后一个就是答案。递归左子树时，会遍历到最左边的节点，但不一定是最底层。所以递归是优先左边搜索，找深度最大的叶子节点。

code

层序遍历

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function findBottomLeftValue($root) {
        $res = [];
        //构造队列
        $queue = new SplQueue();
        //头结点入队列
        $queue->enqueue($root);
        //层数记录
        $deep = 0;
        while(!$queue->isEmpty()){
            //计算当前层队列节点总数
            $count = $queue->count();
            $temp = [];
            $deep++;
            //遍历当前层队列节点
            while($count--){
                //队列节点出队列
                $node = $queue->dequeue();
                //收集节点
                $temp[] = $node->val;
                if($node->left != null){
                    //左孩子入队列
                    $queue->enqueue($node->left);
                }
                if($node->right != null){
                    //右孩子入队列
                    $queue->enqueue($node->right);
                }
            }
            //收集当前层节点
            $res[] = $temp;
        }
        //print_r($res);
        //最底层第一个元素就是二叉树的 最底层 最左边 节点
        return $res[$deep-1][0];
    }
}

递归法

class Solution {
    private $maxDepth = PHP_INT_MIN;//记录最大深度
    private $result;//节点值
    private $depth = 0;//记录实时深度
    /**
     * @param TreeNode $root
     * @return Integer
     */
    function findBottomLeftValue($root) {
        //判断叶子结点
        if($root->left == null && $root->right == null){
            //更新最大深度，节点值
            if($this->depth > $this->maxDepth){
                $this->maxDepth = $this->depth;
                $this->result = $root->val;
            }
            return $this->result;
        }
        //遍历左子树
        if($root->left){
            $this->depth++;
            $this->findBottomLeftValue($root->left);
            //回溯
            $this->depth--;
        }
        //遍历右子树
         if($root->right){
            $this->depth++;
            $this->findBottomLeftValue($root->right);
            //回溯
            $this->depth--;
        }
        return $this->result;
    }
}

112. 路径总和

解题方法

使用任意遍历顺序遍历二叉树，遍历过程中使用sum变量遍历累加节点值，当碰到叶子节点时，使用res数组收获当前路径的总和。遍历完成后，判断targetsum是否存在res数组中即可。

code

递归法

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $targetSum
     * @return Boolean
     */
    function hasPathSum($root, $targetSum) {
        if($root == null) return false;
        $sum = 0;//计数
        $res = [];//获取每条路径总数
        $this->getPathSum($root, $sum, $targetSum, $res);
        //最后判断目标值是否在数值中
        if(in_array($targetSum,$res)) return true;
        return false;
    }

    function getPathSum($cur, $sum, $targetSum, &$res){
        $sum += $cur->val;
        if($cur->left == null && $cur->right == null){
            //判断到了叶子节点时获取每条路径总数
            $res[] = $sum;
            return;
        }
        if($cur->left != null){
            $this->getPathSum($cur->left, $sum, $targetSum,$res);
        }

        if($cur->right != null){
            $this->getPathSum($cur->right, $sum, $targetSum,$res);
        }
    }
}

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

解题方法

从后序数组找到根节点。后序数组中，最后的元素一定是二叉树根节点,找到根节点作为切割中序数组的切割垫
根据后序数组找到的根节点切割中序数组找到左子树与右子树。遵循左闭右开原则，从[0，根节点)截取的是二叉树左子树，从[根节点 + 1，count(inorder(中序数组)))截取的是二叉树右子树
递归构造左右子树
array_slice切割的索引值就是遵循左闭右开原则。

code

递归法

class Solution {

    /**
     * @param Integer[] $inorder
     * @param Integer[] $postorder
     * @return TreeNode
     */
    function buildTree($inorder, $postorder) {
        return $this->traversal($inorder, $postorder);
    }

    function traversal($inorder, $postorder){
        if(count($postorder) == 0) return null;
        //弹出后续数组中的根节点
        $rootVal = array_pop($postorder);
        //构造二叉树
        $tree = new TreeNode($rootVal);
        $endIndex = 0;
        //寻找中序数组中的根节点索引
        foreach($inorder as $key => $val){
            if($val == $rootVal){
                $endIndex = $key;
                break;
            }
        }
        //切割数组，中序数组的左孩子部分，后序数组的左孩子部分
        $tree->left = $this->traversal(array_slice($inorder, 0, $endIndex), array_slice($postorder, 0, $endIndex));
        //切割数组，中序数组的右孩子部分，后序数组的右孩子部分
        $tree->right = $this->traversal(array_slice($inorder, $endIndex + 1), array_slice($postorder, $endIndex));
        return $tree;
    }
}