坐下,这些都是二叉树的基本操作!

春招来了,辞了职在家里准备再找份实习工作。相信大家,尤其是大三、大四的同学都经常在招聘要求上看到这样一条要求:熟悉常见的数据结构与算法。常见的数据结构通常有:链表二叉树,如果要求再高点,可能会让你实现红黑树AVL树这种高级的数据结构。由此可见,数据结构与算法还是比较重要的,最近也是在复习这方面的知识。本篇为复习过程中遇到过的总结,同时也给各位跟我一样准备面试的同学一份参考。另外,由于篇幅有限,本篇的重点在于二叉树的常见算法以及实现。

常见的二叉树实现代码

之前写过相关的文章,是关于如何创建及遍历二叉树的,这里不再赘述。提供链接给各位感兴趣的小伙伴,点此跳转

翻转二叉树

对于一棵二叉树,翻转它的左右子树,如下图所示:

坐下,这些都是二叉树的基本操作!下面来分析具体的实现思路:
  • 对于根结点为空的情况
    这种情况需要排除,因为null不是一个对象,不可能存在左右子树并且可以翻转的情况
  • 对于一棵只有一个根结点的二叉树
    emmm,这种情况也可以翻转,因为此时根结点左右子树为null,交换左右子树其实也就是在交换两个null,理论上是翻转了,但实际上我们看到的和没有翻转之前的结果是一样的
  • 对于一棵具有两个或两个以上结点的二叉树,此时二叉树可以表示为如下的图像:
坐下,这些都是二叉树的基本操作!
可以看出,无论是只有左子树还是只有右子树都可以进行翻转。这句话等价于,为空的子树可以和不为空的子树进行交换,也就是不对为空的子树进行特殊处理

分析过程

其实这样我们还是不知道二叉树是如何翻转的,我们可以用第一张图的二叉树为例子,看一下翻转的具体过程。

  1. 首先我们需要对根结点进行判空处理,在根结点不为空的情况下存在左右子树(即使左右子树为空),然后交换左右子树;
坐下,这些都是二叉树的基本操作!2. 把根结点的左子树当成左子树的根结点,对当前根结点进行判空处理,不为空时交换左右子树;坐下,这些都是二叉树的基本操作!坐下,这些都是二叉树的基本操作!3. 把根结的右子树当成右子树的根结点,对当前根结点进行判空处理,不为空时交换左右子树;坐下,这些都是二叉树的基本操作!4. 重复步骤23,最后二叉树变为原来的镜像结构,结果可以参考文章第一张示意图。

示例代码

根据上面的推理过程我们可以得出如下的代码:

function reverseTree(root){
    if( root !== null){
        [root.left, root.right] = [root.right, root.left]
        reverseTree(root.left)
        reverseTree(root.right)
    }
}

虽然推理过程比较复杂(也可能是写的比较啰嗦。。),但是仔细观察代码,这和遍历的代码似乎也没多大差别,只是把输出结点变为了交换结点。

判断二叉树是否完全对称

一棵左右完全对称的二叉树是这样的:

坐下,这些都是二叉树的基本操作!那到底如何判断呢?
  • 根结点为空时,此时为一棵空二叉树,满足对称条件(-_-||)
  • 只有一个根结点时,左右子树都为null,满足左右对称条件
  • 只有两个结点时,此时左右子树必定有一个为空,不可能存在对称的情况
  • 结点数在三个及三个以上时,二叉树有对称的可能。

按照我们正常的思维,看对称与否,首先看左边,然后看右边,最后比较左右是否相等。同时我们注意到,在二叉树深度比较大的时候,我们光是比较左右是不够的。可以观察到,我们比较完左右以后还需要比较左的左右的右,比较左的右右的左

分析过程

这么看是比较绕,接下来我们来看图分析:

  1. 先比较根结点左右孩子坐下,这些都是二叉树的基本操作!
  2. 左子树根结点的左孩子右子树根结点的右孩子进行比较坐下,这些都是二叉树的基本操作!
  3. 左子树根结点的右孩子右子树根结点的左孩子进行比较坐下,这些都是二叉树的基本操作!
  4. 重复以上过程...

示例代码

function isSymmetrical(pRoot)
{
    // write code here
    if(!pRoot){
        return true
    }
    return funC(pRoot.left, pRoot.right)
}
 
function funC(left, right){
     
    if(!left){
        return right === null
    }
     
    if(!right){
        return false
    }
     
    if(left.val !== right.val){
        return false
    }
     
    return funC(left.right, right.left) && funC(left.left, right.right)
}

求二叉树的深度

分析过程

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

示例代码

function deep(root){
    if(!root){
        return 0
    }
    let left = deep(root.left)
    let right = deep(root.right)
    return left > right ? left + 1 : right + 1
}

求二叉树的宽度

二叉树的宽度是啥?我把它理解为具有最多结点数的层中包含的结点数,比如下图所示的二叉树,其实它的宽度就是为4:

坐下,这些都是二叉树的基本操作!

分析过程

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

  1. 算出第一层的结点数,保存
  2. 算出第二层的结点数,保存一二层中较大的结点数
  3. 重复以上过程

示例代码

根据分析过程,我们可以利用队列这种数据结构来实现这个算法,代码如下:

function width(root){
    if(!root){
        return 0
    }
    let queue = [root], max = 1, deep = 1
    while(queue.length){
        while(deep--){
            let temp = queue.shift()
            if(temp.left){
                queue.push(temp.left)
            }
            if(temp.right){
                queue.push(temp.right)
            }
        }
        deep = queue.length
        max = max > deep ? max : deep
    }
    return max
}

未完待续...