数据结构与算法（二） 02-对称二叉树和二叉树镜像

傷城~ 2023-01-03 04:24 121阅读 0赞

### 文章目录 ###

*  对称二叉树、二叉树镜像、二叉搜索树、二叉树深度
 *   *  1 对称二叉树
     *   *  题目
         *  思路
         *  代码
         *  考察点
     *  2 二叉树的镜像
     *   *  题目
         *  思路
         *  代码
     *  3 二叉搜索树
     *   *  3.1 二叉搜索树概述
         *  3.2 二叉搜索树的第k个节点
         *   *  题目
             *  思路
             *  代码
         *  3.3 二叉搜索树的后序遍历
         *   *  思路
             *  代码
     *  4 二叉树的深度
     *   *  4.1 二叉树的最大深度
         *   *  题目
             *  思路
             *  代码
         *  4.2 二叉树的最小深度
         *   *  题目
             *  思路
             *  代码

--------------------

# 对称二叉树、二叉树镜像、二叉搜索树、二叉树深度 #

## 1 对称二叉树 ##

### 题目 ###

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

### 思路 ###

二叉树的右子树是二叉树左子树的镜像二叉树。

镜像二叉树：两颗二叉树根结点相同，但他们的左右两个子节点交换了位置。

对称二叉树满足以下条件：

*  根节点相同
 *  左子树的左节点与右子树的右节点相同
 *  左子树的右节点与右子树的左节点详图

### 代码 ###

`没想出来`

### 考察点 ###

*  二叉树
 *  抽象问题形象化

## 2 二叉树的镜像 ##

### 题目 ###

操作给定的二叉树，将其变换为源二叉树的镜像。

源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5

### 思路 ###

递归交换二叉树所有节点的左右节点位置

### 代码 ###

function Mirror(node) { 
      if (node) { 
        const tmp = node.left;
        node.left = node.right;
        node.right = temp;
        Mirror(node.left);
        Mirror(node.right);
      }
    }

## 3 二叉搜索树 ##

### 3.1 二叉搜索树概述 ###

**设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。**

在二叉搜索树中：

*  若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值；
 *  若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值；
 *  任意结点的左、右子树也分别为二叉搜索树
    
        得益于二叉搜索树的性质，当使用中序遍历来访问一棵二叉搜索树上的所有结点时，最后得到的访问序列恰好是所有结点关键字的升序序列。

### 3.2 二叉搜索树的第k个节点 ###

#### 题目 ####

给定一棵二叉搜索树，请找出其中的第k小的结点。 例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

#### 思路 ####

二叉搜索树的中序遍历即排序后的节点，本题实际考察二叉树的遍历。

#### 代码 ####

递归实现

非递归实现

### 3.3 二叉搜索树的后序遍历 ###

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

#### 思路 ####

1.  后序遍历分成三部分：
    
     *  最后一个节点为根节点
     *  左子树的值比根节点小
     *  右子树的值比根节点大
2.  先检验左子树，左侧比根节点小的值均判定为左子树
3.  除最后一个节点和左子树外的其他值为右子树，若右子树有一个比根节点小，则返回false。
4.  若存在左右子树，递归检测是否规范。

#### 代码 ####

## 4 二叉树的深度 ##

### 4.1 二叉树的最大深度 ###

#### 题目 ####

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 `[3,9,20,null,null,15,7]`，

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

#### 思路 ####