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

翻转|镜像二叉树

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

941251071-5be058796bcaa_articlex.png

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

只有右子树时，二叉树深度为右子树深度加 1

同时存在左右子树时，二叉树深度为左右子树中深度最大者加 1

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

getTreeDepth(node){let leftD =1let rightD =1function 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}

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

分析过程

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

算出第一层的结点数，保存

算出第二层的结点数，保存一二层中较大的结点数

重复以上过程

getTreeWidth (node) {let queue = [node]let max = 1let width = queue.lengthwhile (queue.length) {width=queue.lengthwhile (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。

递归判断根的左子树是否为平衡二叉树

递归判断根的右子树是否为平衡二叉树

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

首先，判断它的左子树是否为平衡二叉树

然后在判断它的右子树是否为平衡二叉树

判断它们是否为平衡二叉树的同时，记录它们的左右子树的深度

最后在判断以这个结点为根的树是否为平衡二叉树

在排序数组中查找元素的第一个和最后一个位置（中等）给定一个按照升序排列的整数数组 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