算法随笔 — 树结构基础 — 二叉树

小咪咪 2023-01-22 03:55 19阅读 0赞

## 二叉树是什么 ##

二叉树是一种重要的树形结构  
![二叉树概念图][20210517142734990.png]  
n叉树的n是指有最多连接数的节点的连接数

二叉树具有如下**性质**

*  每个节点的度最多为2 (0 ≤ 实际节点的连接数 ≤ 2)
 *  度为0的节点比度为2的节点多一个  
    `证明`: 根据度的定义可知，度为1的节点有一条边，度为2的节点有两条边 令 n 0 为 有 0 条 边 的 节 点 数 、 n 1 为 有 1 条 边 的 节 点 数 、 n 2 为 有 2 条 边 的 节 点 数 ∵ n 个 节 点 的 树 有 n − 1 条 边 ∴ n 0 + n 1 + n 2 = n 1 + 2 n 2 + 1 n 0 = n 2 + 1 令n\_0为有0条边的节点数、n\_1为有1条边的节点数、 n\_2为有2条边的节点数\\\\ \\because n个节点的树有n-1条边 \\\\ \\therefore n\_0+n\_1+n\_2=n\_1+2n\_2+1 \\\\ n\_0=n\_2+1 令n0为有0条边的节点数、n1为有1条边的节点数、n2为有2条边的节点数∵n个节点的树有n−1条边∴n0\+n1\+n2=n1\+2n2\+1n0=n2\+1

二叉树遍历:

*  前序：根 -> 左 -> 右
 *  中序：左 -> 根 -> 右
 *  后序：左 -> 右 -> 根
 *  … (在后续文章中补充)

> 二叉树的拓展概念

**完全二叉树**  
只有在最后一层的右侧缺少的树  
![完全二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]  
完全二叉树是一个很有意思的也很有用的树形结构，它有一个特点，一个编号为i的节点，其左子编号为:  2 ∗ i 2\*i 2∗i，其右子编号为: 2 ∗ i + 1 2\*i+1 2∗i\+1

根据此性质，我们可以不用通过对象的形式创建节点和建立节点之间的连接，而是可以利用连续空间存储(如数组)

通过这个性质我们可以实现一二维的转换  
![树形结构和数组的转换][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]  
当然了，从0开始计数的话编号为i的节点的左子编号是 2 ∗ i + 1 2\*i+1 2∗i\+1，右子编号是 2 ∗ i + 2 2\*i+2 2∗i\+2，性质没有发生变化，只是做了一下数学上的转换

当然，这种通过计算得到节点和通过记录得到节点的方式没有绝对的好与坏，具体问题具体分析。当需要节省空间的时候我们可以考虑利用计算式的结构存储，当需要节省时间的时候我们可以考虑利用记录式的方式存储

**满二叉树**  
没有度为1的节点的二叉树  
![满二叉树][20210517145025155.png]  
**完美二叉树**  
没有度为1的节点同时每一层都满的二叉树  
![完美二叉树][20210517145120963.png]

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

## 二叉树作用 ##

*  **完全二叉树**
    
     *  维护集合最值
        
         *  堆
         *  优先队列
 *  **多叉树/森林**
    
     *  字符串及相关转换问题
        
         *  字典树
         *  AC自动机
     *  连通性问题
        
         *  并查集
 *  **二叉排列树**
    
     *  语言标准库中重要的数据检索容器的底层实现
        
         *  AVL树
         *  2-3树
         *  红黑树
     *  文件系统、数据库、底层重要数据结构
        
         *  B-树/B+树 (读作“B树和B加树”)

**练习递归**

*  数学归纳法  
    不探究具体执行过程，而是用数学证明结果正确  
     已 知 k 0 正 确 假 设 k i 正 确 ， 由 此 可 推 导 k i + 1 正 确 综 上 ， 证 明 成 立 已知k\_0正确 \\\\ 假设k\_i正确，由此可推导k\_\{i+1\}正确 \\\\ 综上，证明成立 已知k0正确假设ki正确，由此可推导ki\+1正确综上，证明成立
 *  赋予递归函数一个明确的意义
 *  思考边界条件
 *  实现递归过程

eg.斐波那契数列的递归实现

function fib (n:number) { 
      if (n <= 2) return n
      return fib(n-1) + fib(n-2)
    }

1. 已 知 k 0 正 确 ( f i b ( 0 ) = = 0 ) 2. 假 设 f i b ( n − 1 ) 和 f i b ( n − 2 ) 能 得 到 第 n − 1 项 和 第 n − 2 项 斐 波 那 契 的 值 ， 那 么 f i b ( n ) 就 能 得 到 正 确 的 值 3. 联 立 以 上 2 步 ， 该 递 归 程 序 成 立 1.已知k\_0正确 (fib(0) == 0) \\\\ 2.假设fib(n-1)和fib(n-2)能得到第n-1项和第n-2项斐波那契的值，\\\\ 那么fib(n)就能得到正确的值 \\\\ 3.联立以上2步，该递归程序成立 1.已知k0正确(fib(0)==0)2.假设fib(n−1)和fib(n−2)能得到第n−1项和第n−2项斐波那契的值，那么fib(n)就能得到正确的值3.联立以上2步，该递归程序成立

eg. 二叉树的前序遍历

*  函数意义：前序遍历以root为根节点的二叉树
 *  边界条件：root为空时不需要遍历
 *  递归过程：前序遍历(递归调用)左子树，前序遍历(递归调用)右子树

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

## 左孩子右兄弟表示法 ##

“左孩子右兄弟表示法”是二叉树用来表示“森林”的一种方式，通过这种表示法可以大大的节省空间，同时在此规则下，任何树都可以转换为二叉树 (AlphaGo也用到了这种数据结构)  
![左孩子右兄弟表示法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]  
证明二叉树比n(n≥2)叉树更省空间：  
 设 一 个 有 n 个 节 点 的 k 叉 树 则 其 总 共 有 n k 个 指 针 域 ， n − 1 条 边 无 效 的 指 针 域 = n k − ( n − 1 ) = ( k − 1 ) n + 1 ∴ k 越 大 浪 费 的 空 间 越 多 当 k = 2 ， 即 为 二 叉 树 时 无 效 的 指 针 域 = ( 2 − 1 ) n + 1 = n + 1 设一个有n个节点的k叉树 \\\\ 则其总共有nk个指针域，n-1条边 \\\\ 无效的指针域 = nk-(n-1)=(k-1)n+1 \\\\ \\therefore k越大浪费的空间越多 \\\\ 当k=2，即为二叉树时 \\\\ 无效的指针域=(2-1)n+1=n+1 设一个有n个节点的k叉树则其总共有nk个指针域，n−1条边无效的指针域=nk−(n−1)=(k−1)n\+1∴k越大浪费的空间越多当k=2，即为二叉树时无效的指针域=(2−1)n\+1=n\+1

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

## 习题 ##

建议一边看一边动手练习

本文的解题方式优先用递归，虽然有的习题可以用更优秀的解法，但是本文核心还是练习递归 (有些题目一看就知道是什么意思的就不放题目截图了)

> ### leetCode 144 二叉树的前序遍历 ###

前文提到过，二叉树的前序遍历顺序是：根 => 左 => 右

此处的函数递归有以下含义：

*  函数意义：前序遍历以 root 为根节点的二叉树
 *  边界条件：root 为空时不需要遍历
 *  递归过程：前序遍历左子树，前序遍历右子树

function preorderTraversal(root: TreeNode | null): number[] { 
      if (!root) return []
      const ans: number[] = []
      
      const run = (node: TreeNode) => { 
        if (!node) return
        ans.push(node.val)
        if (node.left) run(node.left)
        if (node.right) run(node.right)
      }
      run(root)
      
      return ans
    }

![二叉树前序遍历结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 3]  
leetCode 145 二叉树的后序遍历

在讲栈的文章中我们用栈去解过这道题，读者可以试着自己用递归来实现，其实就是一个照葫芦画瓢的过程

> ### leetCode 589 N叉树的前序遍历 ###

本题的递归函数含义：

*  函数意义：前序遍历以 root 为根节点的N叉树
 *  边界条件：root 为空时不需要遍历
 *  递归过程：前序遍历root下的每一颗子树

function preorder(root: Node| null): number[] { 
      if (!root) return []
      const ans: number[] = []
      const run = (node: Node) => { 
        if (!node) return
        ans.push(node.val)
        for (let n of node.children) run(n)
      }
      run(root)
      return ans
    }

![N叉树的前序遍历结果][N]

> ### leetCode 226 翻转二叉树 ###

本题的递归函数含义：

*  函数意义：翻转以root为节点的二叉树
 *  边界条件：root为空时不需要遍历; 当前节点为叶子节点的时候不需要进行交换;
 *  递归过程：翻转左右子节点，翻转左子树，翻转右子树

function invertTree(root: TreeNode | null): TreeNode | null { 
      if (!root) return null
      if (root.left || root.right) [root.left, root.right] = [root.right, root.left]
      invertTree(root.left)
      invertTree(root.right)
      return root
    }

![翻转二叉树结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 4]

> ### leetCode 剑指offer 32 - I 从上到下打印二叉树 ###

本题的注意点有:

1.  在递归过程中要记录当前节点要放到第几个数组中
2.  用队列进行层序遍历

![打印二叉树题解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 5]

function levelOrder(root: TreeNode | null): number[] { 
      if (!root) return []
      const ans: number[] = [], queue: TreeNode[] = [root]
      let node, len
      const run = () => { 
        len = queue.length
        for (let i = 0; i < len; i++) { 
          node = queue.shift()
          ans.push(node.val)
          if (node.left) queue.push(node.left)
          if (node.right) queue.push(node.right)
        }
        if (queue.length) run()
      }
      run()
      return ans
    }

![从上到下打印二叉树结果1][1]

> ### leetCode 剑指offer 32 - II 从上到下打印二叉树 II ###

这题和上题思路类似，只是输出格式稍微变化了一下

![从上到下打印二叉树II题目][II]

function levelOrder(root: TreeNode | null): number[][] { 
      if (!root) return []
      const ans: number[][] = [], queue: TreeNode[] = [root]
      let node, len
      
      const run = (k: number) => { 
        if (k === ans.length) ans[k] = []
        len = queue.length
        for (let i = 0; i < len; i++) { 
          node = queue.shift()
          ans[k].push(node.val)
          if (node.left) queue.push(node.left)
          if (node.right) queue.push(node.right)
        }
        if (queue.length) run(k + 1)
      }
      run(0)
      return ans
    }

![从上到下打印二叉树II结果][II 1]

> ### leetCode 剑指offer 32 - III 从上到下打印二叉树 III ###

这题和上题类似，只是要求第一行从左到右打印，第二行从右到左打印，以此类推，这里不展开细节

function levelOrder(root: TreeNode | null): number[][] { 
      if (!root) return []
      const ans: number[][] = [], queue: TreeNode[] = [root]
      let node, len
      const run = (k = 0) => { 
        if (k === ans.length) ans[k] = []
        len = queue.length
        for (let i = 0; i < len; i++) { 
          node = queue.shift()
          if (k % 2 === 1) { 
            ans[k].unshift(node.val)
          } else { 
            ans[k].push(node.val)
          }
          if (node.left) queue.push(node.left)
          if (node.right) queue.push(node.right)
        }
        if (queue.length) run(k + 1)
      }
      run()
      return ans
    }

![从上到下打印二叉树III][III]

> ### leetCode 110 平衡二叉树 ###

题目：判定一棵树是否是平衡二叉树(左右子树高度不超过1)

![平衡二叉树题解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 6]

function isBalanced(root: TreeNode | null): boolean { 
      if (!root) return true
      // 获取一棵树的高度
      // 如果不平衡，返回负数
      const getHeight = (node: TreeNode) => { 
        if (!node) return 0
        const l = getHeight(node.left)
        const r = getHeight(node.right)
        // 左子树或者右子树不平衡
        if (l < 0 || r < 0) return -2
        // 左子树和右子树比较不平衡
        if (Math.abs(l - r) > 1) return -2
        return Math.max(l, r) + 1
      }
      return getHeight(root) >= 0
    }

![平衡二叉树结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 7]

> ### leetCode 112 路径总和 ###

题目：给定一个值，从根节点走到叶子节点，判断是否在路上有累加和为给定值的路

*  边界条件
    
     *  根为空时返回 false
     *  判断当前节点是否为叶子节点，若是，返回 return root.val === targetSum
 *  递归过程
    
    1.  若左子树存在并且找到 targetSum - 当前节点.val === targetSum
    2.  右子树同上
    3.  若左右子树都找不到，返回 false

function hasPathSum(root: TreeNode | null, targetSum: number): boolean { 
      if (!root) return false
      // 叶子节点
      if (!root.left && !root.right) return root.val === targetSum
      // 若左子树找到，返回 true
      if (root.left && hasPathSum(root.left, targetSum - root.val)) return true
      // 若右子树找到，返回 true
      if (root.right && hasPathSum(root.right, targetSum - root.val)) return true
      return false
    }

![路径总和结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 8]

> ### leetCode 105 从前序与中序遍历构造二叉树 ###

![从前序和中序遍历构造二叉树题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 9]  
递归思路：

1.  先从前序中找到根
2.  根据找到的根在中序中还原左子 (递归建立)
3.  同理恢复右子 (递归建立)

function buildTree(preorder: number[], inorder: number[]): TreeNode | null { 
      if (!preorder.length) return null
      const root = new TreeNode(preorder[0])
      const idx = inorder.indexOf(preorder[0])
      //* 恢复左子树
      root.left = buildTree(preorder.slice(1, idx + 1), inorder.slice(0, idx))
      //* 恢复右子树
      root.right = buildTree(preorder.slice(idx + 1), inorder.slice(idx + 1))
      return root
    }

![从前序与中序遍历二叉树结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 10]  
leetCode 106 从中序与后序遍历构造二叉树

道理和本题一样，读者可自行尝试

> ### leetCode 222 完全二叉树节点个数 ###

本题解题思路和前面的层序遍历是类似的，所以就不再赘述了

function countNodes(root: TreeNode | null): number { 
      if (!root) return 0
      let ans = 0, len = 0
      const queue: TreeNode[] = [root]
      
      const run = () => { 
        len = queue.length
        ans += len
        for (let i = 0; i < len; i++) { 
          if (queue[0].left) queue.push(queue[0].left)
          if (queue[0].right) queue.push(queue[0].right)
          queue.shift()
        }
        if (queue.length) run()
      }
      run()
      
      return ans
    }

![完全二叉树结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 11]

> ### leetCode 剑指offer 54 找到二叉搜索树中第k大的节点 ###

这道题的解法有两个思路，先介绍第一个

前文介绍过树的层序遍历，其中的中序遍历是：左 => 根 => 右，而二叉搜索树有个特点，一个节点的左节点比当前节点小，右节点比当前节点大，因此对二叉搜索树使用中序遍历时就能得到一个有序序列

function inorder(node: TreeNode, ans: number[]) { 
      if (!node) return
      inorder(node.left, ans)
      ans.push(node.val)
      inorder(node.right, ans)
    }
    function kthLargest(root: TreeNode | null, k: number): number { 
      if (!root) return 0
      const ans: number[] = []
      inorder(root, ans)
      return ans[ans.length - k]
    }

![leetCode 剑指offer 54结果1][leetCode _offer 54_1]  
第二个思路是利用搜索二叉树的性质

令该搜索二叉树的右子树数量为 cnt\_r，则

*  当 k ≤ cnt\_r 时，目标节点在右子树
 *  当 k = cnt\_r + 1 时，目标节点是根节点
 *  当 k > cnt\_r + 1 时，目标节点在左节点

找出节点位置后，如果在左右子树，则对其进行中序遍历再定位目标，如果是根则直接返回根

function counter(node: TreeNode, count = 0) { 
      if (!node) return 0
      return count + counter(node.left) + counter(node.right) + 1
    }
    function getInorder(node: TreeNode | null, ans: number[] = []) { 
      if (!node) return
      getInorder(node.left, ans)
      ans.push(node.val)
      getInorder(node.right, ans)
    }
    function kthLargest(root: TreeNode | null, k: number): number { 
      if (!root) return 0
      const ans: number[] = []
      const count = counter(root.right)
      // 在右子树
      if (k <= count) { 
        getInorder(root.right, ans)
        return ans[ans.length - k]
      } else if (k === count + 1) { 
        return root.val
      }
      // 在左子树
      getInorder(root.left, ans)
      return ans[ans.length - k + count + 1]
    }

![leetCode 剑指offer 54结果2][leetCode _offer 54_2]

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

## 结语 ##

感谢支持！

[20210517142734990.png]: /images/20221020/57aa0bc23f01422291fcfb168aae5d5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]: /images/20221020/678e45bf380b4ea0925b13ce2ab6e3ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]: /images/20221020/1dfd143b06ce4b67b8f361726f587fce.png
[20210517145025155.png]: /images/20221020/554704e560fe4a8e92d85d8747250857.png
[20210517145120963.png]: /images/20221020/50602cb39bd4493a81f02ecf5d216c86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]: /images/20221020/abe76be5c87b4faab858e5295355806d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 3]: /images/20221020/d0e979ab7ca543cf9cded32b9d2d0f4a.png
[N]: /images/20221020/7e16dad651214ecb8b2c06071c433dac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 4]: /images/20221020/4885602e469a4791920ff5774c34ec0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 5]: /images/20221020/ddb0cafb6911413ebfdd00175a853967.png
[1]: /images/20221020/44f7ca715c22406b9e3c87246af5e841.png
[II]: /images/20221020/766dde82c12a4dba96c05f77b028cc88.png
[II 1]: /images/20221020/5931e7b780854cc4afbc414dcaf73866.png
[III]: /images/20221020/ad64f0069f5543158246fa6b8b604682.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 6]: /images/20221020/1f66f0c61a434abd88dd2929867aac8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 7]: /images/20221020/64e27610038440138c32d4c72f11176c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 8]: /images/20221020/36829d0721674d9bab1b1d9f3ff840a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 9]: /images/20221020/d41be734f0704d1a9aec3b42d7cd2095.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 10]: /images/20221020/ef3dbdcac19d449fab2f9cea6968f2be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 11]: /images/20221020/b04c8e3ec3b64f1da3f08dc814f73576.png
[leetCode _offer 54_1]: /images/20221020/2698cbd3d1454e04a050b4fb97954e13.png
[leetCode _offer 54_2]: /images/20221020/55f841a1c16b47f88e42d569b20e952a.png