Leetcode 二叉树题目集合 (看完这个面试不会做二叉树题,辣条给你！！！！！)（上）

2022-11-16 105

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Leetcode 二叉树题目集合 (看完这个面试不会做二叉树题,辣条给你！！！！！)

✏️Leetcode 经典二叉树题目集合

开题：这位同志，麻烦你手写一个红黑树出来...... 告辞！！！！！

✏️1. 二叉树的前序遍历（leetcode144）

前序遍历，先访问根结点，然后在访问左子树，最后访问右子树。可以利用栈的特点，这里我结合了队列和栈的特点来实现。先压入树，取出根节点。先把根节点值 push 到队列中，然后把右子树压入栈中，最后压入左子树。返回队列。当然你可以调整成你想要的实现方式。(只要前中后序顺序理解正确即可)

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * [@return](https://learnku.com/users/31554) Integer[]
     */
    function preorderTraversal($root) {
        $res=[];
        $list=[];
        array_unshift($res,$root);
        while(!empty($res)){
           $current=array_shift($res);
           if($current==null) continue;
            array_push($list,$current->val);
            array_unshift($res,$current->right);
            array_unshift($res,$current->left);           
        }
        return $list; 
    }
}

✏️2. 二叉树的中序遍历 (leetcode94)

/**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $res=[];
        $this->helper($root,$res);
        return $res;
    }
    function helper($root,&$res){
        if($root !=null){
            if($root->left !=null) $this->helper($root->left,$res);
            array_push($res,$root->val);
            if($root->right !=null)  $this->helper($root->right,$res);
        }
    }

或者不用递归

/**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $res=[];
        $list=[];
        while(!empty($list) ||  $root !=null){
            while($root != null){
                array_unshift($list,$root);
                $root=$root->left;
            }
            $root=array_shift($list);
            array_push($res,$root->val);
            $root=$root->right;
        }
        return $res;
    }

✏️3. 二叉树的后序遍历 (leetcode145)

/**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root) {
       $list=[];
        $res=[];
        array_push($list,$root);
        while(!empty($list)){
            $node=array_shift($list);
            if(!$node) continue;
            array_unshift($res,$node->val);
            array_unshift($list,$node->left);
            array_unshift($list,$node->right);
        }
        return $res;
    }
}

✏️4. 二叉树的层次遍历 (leetcode102)

DFS 和 BFS 都可以解，竟然已经要我们按照层打印了，那么先使用 BFS，思路就是先判断树是否是空，不是空加入一个队列的结构中，如果队列不为空，取出头元素，那么当前元素表示的就是当前这一层了，所以只需要遍历这一层里的所有的元素即可，然后下一层....

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if(empty($root)) return [];
        $result = [];
        $queue = [];
        array_push($queue,$root);
        while(!empty($queue)){
            $count = count($queue);
            $leveQueue = [];
            for($i = 0;$i<$count;$i++){
                $node = array_shift($queue);
                array_push($leveQueue,$node->val);
                if($node->left) array_push($queue,$node->left);
                if($node->right) array_push($queue,$node->right);
            }
            array_push($result,$leveQueue);
        }
        return $result;
    }
}

如果使用 DFS 的话，就是一条路走到黑，然后再重新一路路的退回来再找下一路，所以这样的话，每一次我们需要记录一下当前他所在的这个点属于哪一层即可，代码用递归实现。

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if(empty($root)) return [];
        $result=[];
        $this->helper($result,$root,0);
        return $result;
    }
    function helper(&$result,$node,$level){
        if(empty($node)) return ;
        if(count($result)<$level+1){
            array_push($result,[]); //说明当前行没有结果
        }
        array_push($result[$level],$node->val);
        $this->helper($result,$node->left,$level+1);
        $this->helper($result,$node->right,$level+1);
    }
}

✏️5. 二叉树的最大深度 (leetcode104）

/**
     * @param TreeNode $root
     * @return Integer
     */
    function maxDepth($root) {
        if(empty($root)) return 0;
        $left = $this->maxDepth($root->left);
        $right = $this->maxDepth($root->right);
        return $left<$right?  $right+1:$left+1;
        return max($left,$right)+1;
    }

✏️6. 二叉树的最小深度 (leetcode111）

DFS 和 BFS 都可以求解

//BFS
 /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
       if(empty($root)) return 0;
        if(!$root->right) return $this->minDepth($root->left)+1;
        if(!$root->left) return $this->minDepth($root->right)+1;
        $left=$this->minDepth($root->left);
        $right=$this->minDepth($root->right);
        return min($left,$right)+1;     
    }
//DFS
 /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
        if(empty($root)) return 0;
           $left=$this->minDepth($root->left);
          $right=$this->minDepth($root->right);
        if($left==0 || $right==0) return $left+$right+1;
        return min($left,$right)+1;
    }

✏️7. 判断是否是平衡二叉树 (leetcode110）

每一节点的两个子树的深度相差不能超过 1。如果是空树，直接 true。

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    private $result=true;
    function isBalanced($root) {
        if(empty($root)) return true;
        $this->helper($root);
        return $this->result;
    }
    function helper($root)
{
        if(!$root) return ;
        $left=$this->helper($root->left);
        $right=$this->helper($root->right);
        if(abs($left-$right)>1) $this->result=false;
        return max($left,$right)+1;
    }
}

✏️8. 判断是否是对称二叉树 (leetcode101）

1. 两个子节点都是空，那说明他们是对称的返回 true

2. 一个子节点为空，另一个子节点不为空，false

3. 两个子节点都不为空，但是他们不相等，false

4. 两个子节点不为空且相等，继续判断他们的左子树和右子树，把左子树的左子节点和右子树的右子节点进行比较，把左子树的右子节点和右子树的左子节点进行比较

/**
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
      if(empty($root)) return true;
        return $this->helper($root->left,$root->right);
    }
    function helper($l,$r){
       if(!$l && !$r) return true;
        if(!$l || !$r || $l->val != $r->val) return false;
        return $this->helper($l->left ,$r->right) && $this->helper($l->right,$r->left);
    }