专栏首页前端架构讲透学烂二叉树(六):二叉树的笔试题:翻转|宽度|深度
原创

讲透学烂二叉树(六):二叉树的笔试题:翻转|宽度|深度

翻转|镜像二叉树

华为面试题——将二叉树的两个孩子换位置,即左变右,右变左。

90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

递归实现

先序遍历每个结点,翻转每个结点。

下面来分析具体的实现思路:

  • 对于根结点为空的情况 这种情况需要排除,因为null不是一个对象,不可能存在左右子树并且可以翻转的情况
  • 对根不为空的情况,翻转该节点

JavaScript代码实现二叉树翻转

reverseTree (root = this.tree) {
    if (root &&root.data) {
        [root.leftChild, root.rightChild] = [root.rightChild, root.leftChild]
        this.reverseTree(root.leftChild)
        this.reverseTree(root.rightChild)
    }
}

循环,栈存储(DFS,非递归)

本质思想是,左右节点进行交换,循环翻转每个节点的左右子节点,将未翻转的子节点存入栈中,循环直到栈里所有节点都循环交换完为止。

reverseTree3 (node) {
    if (!node) {
        return 0
    }
    let queue = [node]
    while (queue.length) {
        let temp = queue.shift();
        [temp.leftChild, temp.rightChild] = [temp.rightChild, temp.leftChild]
        temp.leftChild && queue.push(temp.leftChild)
        temp.rightChild && queue.push(temp.rightChild)
    }
    return node
}

层序遍历,翻转每层的结点

JavaScript代码实现

reverseTree2 (node = this.tree) {
    let buckets = [[node]]
    let i = 0

    function getChildNode (root, i) {
        if (!root || !root.data) {
            return false
        }
        i++
        if (buckets[i] === undefined) {
            buckets[i] = []
        }
        if (root.leftChild) {
            buckets[i].push(root.leftChild)
            getChildNode(root.leftChild, i)
        }
        if (root.rightChild) {
            buckets[i].push(root.rightChild)
            getChildNode(root.rightChild, i)
        }
    }
    getChildNode(node, i)
    for (let i = 0; i < buckets.length; i++) {
        for(let j=0;j<buckets[i].length;j++){
            if(i>1){
                let parentIndex = buckets[i-1].length-1-Math.floor(i/2)
                buckets[i][j]['parent']=buckets[i-1][parentIndex]
            }
            buckets[i+1].reverse()
            let leftChildIndex = i*2
            let rightChildIndex = i*2+1
            if(buckets[i+1][leftChildIndex]){
                buckets[i][j]['leftChild']=buckets[i+1][leftChildIndex]
            }
            if(buckets[i+1][rightChildIndex]){
                buckets[i][j]['rightChild']=buckets[i+1][rightChildIndex]
            }
            if(i===buckets.length-1){
                break
            }

        }

    }
    return node
}

就是翻转每一层的数据

求二叉树的深度

分析过程

  1. 只有一个根结点时,二叉树深度为1
  2. 只有左子树时,二叉树深度为左子树深度加1
  3. 只有右子树时,二叉树深度为右子树深度加1
  4. 同时存在左右子树时,二叉树深度为左右子树中深度最大者加1

JavaScript求二叉树深度,代码实现

getTreeDepth(node){
    let leftD =1
    let rightD =1
    function getDeep(node){
        if(!node||!node.data){
            return 0
        }
        if(node.leftChild){
            leftD++
            getDeep(node.leftChild)
        }
        if(node.rightChild){
           rightD++
           getDeep(node.rightChild)
        }
    }
    return leftD>rightD?leftD:rightD
}

求二叉树的宽度

二叉树的宽度是啥?我把它理解为具有最多结点数的层中包含的结点数

分析过程

根据上图,我们如何算出二叉树的宽度呢?其实有个很简单的思路:

  1. 算出第一层的结点数,保存
  2. 算出第二层的结点数,保存一二层中较大的结点数
  3. 重复以上过程
getTreeWidth (node) {
    let queue = [node]
    let max = 1
    let width = queue.length
    while (queue.length) {
        width=queue.length
        while (width) {
            let temp = queue.shift()
            if (temp.leftChild) {
                queue.push(temp.leftChild)
            }
            if (temp.rightChild) {
                queue.push(temp.rightChild)
            }
            width--
        }
        max = queue.length > max ? queue.length : max
    }
    return max
}

判断一颗二叉树是否为平衡二叉树

解决思路一:按照前序遍历的路线判断。

  1. 判断以根结点的树是否为二叉平衡树。求出左右子树的高度,判断它们的高度差是否超过了1。
  2. 递归判断根的左子树是否为平衡二叉树
  3. 递归判断根的右子树是否为平衡二叉树

解决思路二:按照后序遍历的路线判断

  • 首先,判断它的左子树是否为平衡二叉树
  • 然后在判断它的右子树是否为平衡二叉树
  • 判断它们是否为平衡二叉树的同时,记录它们的左右子树的深度
  • 最后在判断以这个结点为根的树是否为平衡二叉树

在排序数组中查找元素的第一个和最后一个位置(中等)

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2:

输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]

二分查找分析与思路

按照正常的二分查找思路,循环找到匹配目标数字的下标,继续将右指针变小查找到第一个目标数字。用新的循环从找到的第一个目标数字下标从左往右查找直到最后一个目标数字。(具体的查找思路见伪代码)

/**
 * 二分查找数组中,第一出线目标数据的前后位置, 如果没有返回[-1,-1]
 * @param arr {Array}
 * @param target {Number}
 * @return {number[]}
 */
function searchRange (arr, target) {
    // 声明搜索用的左右指针,初始左指针下标0,右指针下标数组末位nums.length-1;
    let l = 0, r = arr.length - 1
    // 获取数组中间下标pivot = (l + r) / 2;
    let pivot = Math.floor((l + r) / 2)
    // 声明创建结果数组,初始化赋值-1;
    let res = [-1, -1]
    // 循环二分查找,直到左指针大于右指针查找结束
    while (l <= r) {
        // 若中间位置数字小于目标数字,说明目标数字在pivot右边,将左指针l右移赋值为pivot+1;
        if (arr[pivot] < target) {
            l = pivot + 1
            // 若中间位置数字大于目标数字,说明目标数字在pivot左边,将右指针r左移赋值为pivot-1;
        } else if (arr[pivot] > target) {
            r = pivot - 1
            // 若中间位置数字等于目标数字:
        } else {
            // 将pivot作为第一次出现位置存入数组;
            res[0] = pivot
            // 右指针r左移赋值为pivot-1,继续查找相等的数字直到找到第一次出现的位置;
            r = pivot - 1
        }
        // 更新pivot;
        pivot = (l + r) / 2
    }
    // 从第一次出现的位置开始,循环往右查找最后一次出现的位置:
    // 声明pr指针初始赋值为第一次出现位置下标;
    let pr = res[0]
    // 当二分查找已找到目标数字时
    if (pr !== -1) {
        // 循环直到数组越界或者数组当前元素不等于目标元素时结束:
        while (pr <= arr.length - 1 && target === arr[pr]) {
            // 更新最后一次出现位置下标;
            pr += 1
            // 更新最后一次出现位置下标;
            res[1] = pr
        }
    }
    return res
}
console.log(searchRange([-1,5,5,6,8,9,13,22],-2))

参考文章:

使用JavaScript完成二叉树的一些基本操作 https://segmentfault.com/a/1190000016914803

JavaScript二叉树实现和原理完全讲解 www.srcmini.com/1772.html

LeetCode进阶226-翻转二叉树(华为面试题) https://zhuanlan.zhihu.com/p/76818774

面试BAT 却被二叉树秒杀?20 道题帮你一举拿下二叉树算法题 https://zhuanlan.zhihu.com/p/88361872

转载本站文章《讲透学烂二叉树(六):二叉树的笔试题:翻转|宽度|深度》, 请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8289.html

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 本周小结!(二叉树)

    发现大家周末的时候貌似都不在学习状态,周末的文章浏览量和打卡情况照工作日差很多呀,可能是本周日是工作日了,周六得好好放松放松,哈哈,理解理解,但我还不能不更啊,...

    代码随想录
  • 讲透学烂二叉树(四):二叉树的存储结构—建堆-搜索-排序

    数据结构是组织数据的方式,例如树,但是要注意数据结构有两种形式:逻辑结构和存储结构,这两种结构在表示一种数据结构的时候不一定完全相同的,逻辑结构是我们分析数据结...

    周陆军
  • 秋招算法岗面经(主要是撸代码题)

    如果你以后想起,无论何时回想起来,这件事都会让你嘴角带笑的话,你就去做吧。但如果你并不这么认为或者不太确定,那就忘掉它吧,因为你还有大把时间。——《完美陌生人》

    牛客网
  • GitHub标星90K,这份持续霸榜的Leetcode刷题手册到底有多强?

    最近一个读者和我反馈,他坚持刷题2个月,终于去了他梦寐以求的大厂,薪资涨幅非常可观,期间面字节跳动还遇到了原题...并表示目前国内的大厂和一些独角兽,已经越来越...

    烂猪皮
  • 剑指Offer面试题:33.二叉树的深度

      ②如果根结点只有左子树而没有右子树,那么树的深度应该是其左子树的深度加1;同样如果根结点只有右子树而没有左子树,那么树的深度应该是其右子树的深度加1。

    Edison Zhou
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • 给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.blog....

    Jerry Wang
  • 给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

    我今天查资料时无意发现的,https://github.com/CyC2018/CS-Notes

    Jerry Wang
  • C++版 - 剑指Offer 面试题39:二叉树的深度(高度)(二叉树深度优先遍历dfs的应用) 题解

    题目:输入一棵二叉树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 例如:输入二叉树:   ...

    Enjoy233
  • 讲透学烂二叉树(五):分支平衡—AVL树与红黑树伸展树自平衡

    二叉树的最大优点的就是查找效率高,在二叉排序树中查找一个结点的平均时间复杂度是O(log₂N);

    周陆军
  • 秋招时间规划,知识点汇总,以及面试总结一、知识储备二、面试问题三、心态变化四、总结

    秋招已结束,作为一个平时潜水的牛友,很感激牛客网和广大牛友们。在我无知时,给与我知识;在我烦恼时,给与我慰藉;现在自己也拿到了心仪的offer,就简单写写这段时...

    牛客网
  • 深度剖析头条面试真题 | 二叉树那点事儿

    这也是笔者年前面试今日头条时的一道比较基础的二叉树面试题,之前并没有做过,事后发现是 LeetCode 的原题。

    五分钟学算法
  • 这里有 300 篇 Python 与机器学习类原创笔记

    主要包括计算机科学中基本的算法与数据结构,结合算法思想和Leetcode实战,总结介绍。

    好好学java
  • 讲透学烂二叉树(三):二叉树的遍历图解算法步骤及JS代码

    深度优先,前、中、后遍历顺序,就是组合[根左右],移动根的位置,根左右、左根右、左右根,但是我即使代码会写了,还是搞不明白这个根左右与遍历的关系毛线头在哪里,特...

    周陆军
  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • 「经典题目回顾」翻转二叉树!

    今天来回顾一下二叉树,翻转二叉树,绝对是面试题目了,代码不长,又考察对二叉树的操作。

    代码随想录
  • 二叉树知识点回忆以及整理

    在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能...

    静默加载
  • 二叉树:你真的会翻转二叉树么?

    这道题目背后有一个让程序员心酸的故事,听说 Homebrew的作者Max Howell,就是因为没在白板上写出翻转二叉树,最后被Google拒绝了。(真假不做判...

    代码随想录

扫码关注云+社区

领取腾讯云代金券