【二叉树复习】C++ 二叉树复习及题目解析 (1)-Toy模板网

这篇具有很好参考价值的文章主要介绍了【二叉树复习】C++ 二叉树复习及题目解析 (1)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二叉树

树

二叉树

本文将从二叉树的定义和性质以及常用结论出发，来复习关于二叉树的相关知识。最后再贴上相关二叉树题目和解析，来帮助大家更好的复习二叉树。

树

树的性质：

子树不相交。

除了根节点外，其他节点都有且仅有一个父节点。

一颗N 个节点的树有 N-1 个边。

树的表示

孩子兄弟表示法：

 typedef int dataType;
 class Node{
 private:
 Node* _firstChild;
 Node* _nextBrother;
 dataType _data;
 };

二叉树

概念

一颗二叉树是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上左右子树的二叉树组成。

特点：

每个节点最多有两颗子树，即二叉树（最大）度为2.

二叉树的子树有左右之分，而且子树次序不能颠倒。

满二叉树：一个每一层的节点数都是最大值的二叉树，就是满二叉树。如果层数为k，节点数为 2k-1，那么他就是满二叉树。

完全二叉树：只有最后一层可以不满而且节点从左向右排列，其余层数全满的二叉树叫做完全二叉树。效率很高。

满二叉树是一种特殊的完全二叉树。

二叉树的性质：（规定根节点的层数为1）

非空二叉树的第i 层最多有2i-1个节点。

深度为h 的二叉树的最大节点数是2h-1。

度为1的节点个数为0 或者1.

对于任意的一棵二叉树，如果叶子节点（度为0）的个数为n0，度为2 的分支节点个数为n2，那么n0 = n2 + 1；

具有n 个结点的满二叉树的深度为： h = Log2(n+1). 借此可以推断，如果是完全二叉树的节点数为n，那么 Log2(n) < h < Log2(n + 1);

对于n 个节点的完全二叉树，如果从上到下从左到右，对所有节点开始排序，从0 开始。对于序号为i 的节点来说：

i > 0, i 位置节点的双亲序号: (i - 1)/2，i = 0, i 为根节点编号，无双亲节点。

如果 2i + 1 < n, 左孩子序号: 2i + 1, 否则无左孩子。

如果 2i + 2 < n, 右孩子序号: 2i + 2, 否则无右孩子。

存储结构

顺序存储：

使用数组来存储，一般数组只适合存储完全二叉树，否则会产生很多的空间浪费。现实使用时只有堆采用数组来存储。二叉树的顺序存储从物理层面讲是一个数组，从逻辑层面上讲是一个二叉树。

接下来介绍一下堆：

满足ki <= k2i+1 且ki <= k2i+2 的在一位数组中存储数据的集合叫小根堆或者最小堆（因为根节点是最小的），除此外，根节点最大的叫（最）大堆或者大根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是一颗完全二叉树。

链式存储：

分为二叉链和三叉链，二叉链指的是指向左右孩子，三叉链指的是指向左右孩子和父节点。

 //二叉链
 typedef int dataType;
 class BinaryTreeNode{
 private:
 BinaryTreeNode* _pleft;
 BinaryTreeNode* _pright;
 dataType _data;
 };

 //三叉链
 typedef int dataType;
 class BinaryTreeNode{
 private:
 BinaryTreeNode* _pleft;
 BinaryTreeNode* _pright;
 BinaryTreeNode* _pparent;
 dataType _data;
 };

小练习

某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为：

因为n0 = n2 + 1,

所以叶子节点个数为200个。

在具有 2n 个结点的完全二叉树中，叶子节点的个数为：

这时候可以假设，因为度为1的节点个数为0/1，所以首先假设度为1的节点个数为0个。

那么因为n0 = n2 + 1, 叶子节点个数不是整数，pass

假设度为1的节点个数为1个，那么叶子节点个数为：(2n - 1 - 1) / 2 + 1 = n

一棵完全二叉树的节点数位为531个，那么这棵树的高度为:

因为其为完全二叉树，所以假设深度为h，节点数为： 2h-1-1 ~ 2h -1 个，所以可以判断出来应该 h = 10.

一个具有767个节点的完全二叉树，其叶子节点个数为：

和第二个相同的做法，384

树题目：

leetcode 965 单值二叉树。

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

思路1 & 解法：

深度优先搜索算法（Depth First Search)。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

我们就是可以对二叉树进行一次DFS，检查node 和 node的左右节点是否符合。

二叉树的许多题目都可以使用递归来解决问题。
 class Solution {
 public:
  bool isUnivalTree(TreeNode* root) {
      int value = root->val;
      if(!root) return true; //递归终止条件，结点为空
      if(root->left && (root->left->val != value || !isUnivalTree(root->left))) return false; 
    //如果左节点不为空，那么检查左节点的val 是否等于value 如果不等于，那么返回false；
    //如果左节点不为空，那么检查以左节点为根节点是否不符合情况，如不符合，返回false；
      if(root->right && (root->right->val != value || !isUnivalTree(root->right))) return false;
      return true;
  }
 };
复杂度分析：

时间复杂度：O(N)；遍历一遍用了o(n）

空间复杂度：O(N)；因为使用了递归，即为深度优先搜索中需要使用的栈空间。

思路2 & 解法：既然我们可以使用递归来解决问题。也可以使用非递归的方法来解决。

 class Solution {
 public:
  bool isUnivalTree(TreeNode* root) {
      int value = root->val;
      stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()){
          TreeNode* node = s.top();
          s.pop();
          if(node->val != value) return false; // 检查
          if(node->right) s.push(node->right); // 先右节点入栈，右节点后出栈。为前序遍历。
          if(node->left) s.push(node->left); // 再左节点入栈
      }
      return true;
  }
 };

时间复杂度和空间复杂度同上，都是O(N)。

leetcode 103. 二叉树的最大深度

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

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

说明: 叶子节点是指没有子节点的节点。
思路1 & 解法：

同样采用深度优先搜索，但是需要注意的是，我们需要找的递归的规律。

深度depth = max( l , r ) + 1; l 和 r 分别为左子树和右子树的深度。

所以可以很简单的解决：
```
 class Solution {
 public:
  int maxDepth(TreeNode* root) {
      if(!root) return 0;
      return max(maxDepth(root->left), maxDepth(root->right)) + 1;
  }
 };
```
复杂度分析：

时间复杂度O(N)。其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度O(height)。 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
思路2 & 解法：

广度优先搜索（Breadth First Search)：BFS。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）

本题目和传统的广度优先搜索题目不同，传统的广度优先搜索只会在取一个节点进行出队列，但是本题目需要同层所有节点出队列。
```
 class Solution {
 public:
  int maxDepth(TreeNode* root) {
      if(!root) return 0; //检查空树
      queue<TreeNode*> q; //建立队列
      q.push(root); //存储根节点
      int ans = 0; //这个代表我们的深度
      while(!q.empty()) 
      {
          int sz = q.size(); // 因为广度优先搜索要先找到所有的同层的节点
          while(sz > 0) //用循环来将队列里的所有节点都拿出来扩展
          {
              TreeNode* node = q.front();
              q.pop();
              if(node->left) q.push(node->left);
              if(node->right) q.push(node->right);
              sz -= 1;
          }
          ans += 1;
      }
      return ans;
  }
 };
```
时间复杂度分析：O(N)，每个节点都会访问一次。

空间复杂度分析：O(N)，最坏情况，每个位置的节点都会在queue 中存储一遍，所以最坏O(N)。

leetcode 226 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路1 & 解法：

传统递归，我们需要确定

递归终止条件：root 为空，则返回root。

我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。
 class Solution {
 public:
  TreeNode* invertTree(TreeNode* root) {
      if(!root) return root;
      TreeNode* left = invertTree(root->left);
      TreeNode* right = invertTree(root->right);
      root->left = right;
      root->right = left;
      return root;
  }
 };
时间和空间复杂度都是O(N)

思路2 & 解法： DFS：深度优先遍历（stack）

步骤：判空、建立栈并将根节点入栈、循环：选择栈是单次弹出一个还是弹出所有。如果是弹出一个，直接操作然后左右节点入栈。如果是弹出所有，就先记录栈的大小，然后内部循环。最后返回根节点即可。

注：如果想前序遍历，就要先push 右子树，因为先进的后出。

我们默认都是前序遍历，也就是操作->右->左。
 class Solution {
 public:
  TreeNode* invertTree(TreeNode* root) {
      if(!root) return nullptr;//?
      stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()){
          int size = s.size();
          while(size--){
              TreeNode* cur = s.top();
              s.pop();
              TreeNode* tmp = cur->left;
              cur->left = cur->right;
              cur->right = tmp;
              if(cur->right) s.push(cur->right);
              if(cur->left) s.push(cur->left);
          }
      }
      return root;
  }
 };
时间和空间复杂度都是O（N）

时间复杂度O（N）：因为遍历树一遍。

空间复杂度O（N）：因为最坏情况所有的节点都入栈出栈。

思路3 & 解法：

BFS广度优先遍历（queue）（层序遍历）

步骤：和上面完全类似。

 class Solution {
 public:
  TreeNode* invertTree(TreeNode* root) {
      if(!root) return nullptr;//?
      queue<TreeNode*> q;
      q.push(root);
      while(!q.empty()){
          int size = q.size();
          while(size--){
              TreeNode* cur = q.front();
              q.pop();
              TreeNode* tmp = cur->left;
              cur->left = cur->right;
              cur->right = tmp;
              if(cur->left) q.push(cur->left);
              if(cur->right) q.push(cur->right);
          }
      }
      return root;
  }
 };

leetcode100 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路1 & 解法：

传统递归,深度优先搜索DFS(递归解法）：

因为本题目就是判断整棵树相同，可以拆分成判断本节点相同 + 左右子树相同。

首先考虑终止条件，当一方的节点为空的时候，终止，判断另一方是否也为空。

如果两方非空，则直接返回判断左右子树是否相等的函数。
```
 class Solution {
 public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
      // if(!p && !q) return true; //或者写作
      if(!p) return q == nullptr;
      if(p && q && p->val == q->val) return isSameTree(p->left, q->left) &&isSameTree(p->right, q->right);
      else return false;
  }
 };
```
时间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度：O(min⁡(m,n))，其中 m 和 n 分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
思路2 & 解法：

DFS 遍历：

其实DFS遍历的思路都是一样的，判空，建栈入栈，循环，判断是单次弹出一次还是所有，因为本题是判断所以弹出一个即可。

比较麻烦的就是题目里需要判断很多空与非空的条件。在while 循环中，我们如果知道pnode 和 qnode 的左节点都非空，那么直接入栈，后续通过循环即可查二者的值是否相同。如果知道二者左节点都为空，那么也可以判断是true；只有二者左节点一个为空，一个非空的时候才会返回false，所以我们直接用二者== nullptr 的异或操作来判断：一个为空一个非空。

我们不能使用，else if 来判断二者左节点为空进而返回true，会中断我们的循环，直接结束，所以就找出不符合的false情况返回false，如果一直符合情况进而让栈中元素个数为0，我们直接在最后返回true。

注意：先操作(本题目中是判断)，再右节点入栈，再左节点入栈，这是前序遍历。
```
 class Solution {
 public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
      if(!p) return q == nullptr;
      if(!q) return p == nullptr;
      stack<TreeNode*> sp;
      stack<TreeNode*> sq;
      sp.push(p);
      sq.push(q);
      while(!sp.empty() && !sq.empty())
      {
          TreeNode* pnode = sp.top();
          sp.pop();
          TreeNode* qnode = sq.top();
          sq.pop();
 
          if(pnode->val != qnode->val) return false;
          if(pnode->right && qnode->right) sp.push(pnode->right), sq.push(qnode->right);
          else if((pnode->right == nullptr) ^ (qnode->right == nullptr)) returnfalse;
          if(pnode->left && qnode->left) sp.push(pnode->left),sq.push(qnode->left);
          else if((pnode->left == nullptr) ^ (qnode->left == nullptr)) return false;
      }
      return true;
  }
 };
```
时间复杂和空间复杂同上。

BFS 广度优先遍历（queue）

方法完全同上，只是注意：先操作(本题目中是判断)，再左节点入队列，再右节点入队列，这是前序遍历。
```
 class Solution {
 public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
      if(!p) return q == nullptr;
      if(!q) return p == nullptr;
      stack<TreeNode*> qp;
      stack<TreeNode*> qq;
      qp.push(p);
      qq.push(q);
      while(!qp.empty() && !qq.empty())
      {
          TreeNode* pnode = qp.top();
          qp.pop();
          TreeNode* qnode = qq.top();
          qq.pop();
 
          if(pnode->val != qnode->val) return false;
          if(pnode->left && qnode->left) qp.push(pnode->left),qq.push(qnode->left);
          else if((pnode->left == nullptr) ^ (qnode->left == nullptr)) return false;       
          if(pnode->right && qnode->right) qp.push(pnode->right), qq.push(qnode->right);
          else if((pnode->right == nullptr) ^ (qnode->right == nullptr)) returnfalse;
      }
      return true;
  }
 };
```
时间和空间复杂度同上。

leetcode 101 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

思路1 & 解法；

对称二叉树要求左右子树也是对称二叉树，递归到最后就是左右子树（如果左右子树变成叶子节点后）val 相等，最后左右子树都为空，这种情况下返回true。

 class Solution {
 public:
     bool _isSymmetric(TreeNode* left, TreeNode* right) 
    {
         if(!left && !right) return true;
         else if((!left || !right) || left->val != right->val) return false;
         else 
        {
             return _isSymmetric(left->left, right->right) &&
                    _isSymmetric(left->right, right->left);
        }
         
         return true;
    }
     bool isSymmetric(TreeNode* root) {
        return _isSymmetric(root->left, root->right);
    }
 };

思路2 & 解法：

使用BFS，迭代

 class Solution {
 public:
     bool _isSymmetric(TreeNode* left, TreeNode* right)
    {
         queue<TreeNode*> q;
         q.push(left), q.push(right);
         while(!q.empty())
        {
             left = q.front(), q.pop();
             right = q.front(), q.pop();
             if(!left && !right) continue;
             else if(!left || !right || left->val != right->val) return false;
             q.push(left->left);
             q.push(right->right);
 
             q.push(left->right);
             q.push(right->left);
        }
         return true;
    }
     bool isSymmetric(TreeNode* root) {
         return _isSymmetric(root, root);
    }
 };

leetcode 144前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

思路1 & 解法：

常规递归：

 class Solution {
     vector<int> ret;
 public:
     vector<int> preorderTraversal(TreeNode* root) {
         if(!root) return ret;
 
         ret.push_back(root->val);
         preorderTraversal(root->left);
         preorderTraversal(root->right);
 
         return ret;
    }
 };

思路2 & 解法：

常规迭代，利用栈。

 class Solution {
 public:
     vector<int> preorderTraversal(TreeNode* root) {
         vector<int> ret;
         stack<TreeNode*> s;
         s.push(root);
         while(!s.empty())
        {
             TreeNode* node = s.top();
             if(!node) break;
             s.pop();
             
             ret.push_back(node->val);
             if(node->right) s.push(node->right);
             if(node->left) s.push(node->left);
        }
         return ret;
    }
 };

94 中序遍历 & 145 后序遍历

不再解释，因为与前序遍历只有操作位置的不同。

前序：操作->左递归->右递归

中序：左递归->操作->右递归

后序：左递归->右递归->操作

leetcode 572 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路1 & 解法：

暴力解法，我们可以从根节点开始往下查看，一旦发现对应不上就回滚到根节点的左孩子节点或者右孩子节点，直到找到，或者左节点和右节点为空。

这样的时间复杂度非常高，O(N * M)，不做考虑。

思路2 & 解法：

我们可以通过遍历找到一个树的序列，判断子树的序列是否是root 树序列的子序列即可。

但是注意一个问题：我们前序遍历如果遇到空节点会跳过，这会造成判断结果的不准确。应该遍历时标出左孩子节点为空，右孩子节点为空。

第二个问题就是如果判断子序列，这里考虑使用kmp算法。文章来源地址https://www.toymoban.com/news/detail-525713.html

 class Solution {
 public:
     vector<int> sOrder, tOrder;
     int maxElement = INT_MIN;
     int lNull, rNull;
     
     bool isSubtree(TreeNode* s, TreeNode* t) {
         getMaxElement(s);
         getMaxElement(t);
         lNull = maxElement + 1;
         rNull = maxElement + 2;
         getDfsOrder(s, sOrder);
         getDfsOrder(t, tOrder);
 
         return kmp();
    }
 
   //获取树的序列
     void getDfsOrder(TreeNode* root, vector<int>& ret)
    {
         if(!root) return;
         stack<TreeNode*> s;
         s.push(root);
         while(!s.empty())
        {
             TreeNode* node = s.top();
             s.pop();
             ret.push_back(node->val);
 
             if(node->left) s.push(node->left);
             else ret.push_back(lNull);
             if(node->right) s.push(node->right);
             else ret.push_back(rNull);
        }
    }
 
     //为什么要找到最大值，找到最大值后就可以定义rnull 和 lnull 的值了。
     void getMaxElement(TreeNode* root)
    {
         if(!root) return;
         maxElement = max(maxElement, root->val);
         getMaxElement(root->left);
         getMaxElement(root->right);
    }
 
     bool kmp()
    {
         int slen = sOrder.size(), tlen = tOrder.size();
         vector<int> next(tlen, -1);
         for(int i = 1, j = -1; i < tlen; ++i) //i后缀， j 前缀 二者比较
        {
             while(j != -1 && tOrder[i] != tOrder[j + 1]) j = next[j]; 
           //如果末尾字符不匹配前缀后位，那么更新前缀，继续比较
             if(tOrder[i] == tOrder[j + 1]) ++j; //匹配成功 前缀指针后移
             next[i] = j; //修改next数组的值（前后缀统计个数就是以j为准。
        }
         for(int i = 0, j = -1; i < slen; ++i)
        {
             while(j != -1 && sOrder[i] != tOrder[j + 1]) j = next[j];
             if(sOrder[i] == tOrder[j + 1]) ++j;
             if(j == tlen - 1) return true;
        }
         return false;
    }
 
 
 };

到了这里，关于【二叉树复习】C++ 二叉树复习及题目解析 (1)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！