剑指 offer 系列

Mr.Hdd大约 5 分钟...

二叉树相关习题

919.完全二叉树插入器open in new window

题目输入的是一颗使用【二叉链表存储结构的完全二叉树】，然后需要对其进行三个操作：

以层序遍历的方式输出结点
插入一个结点到二叉树，并返回该插入结点的父结点
返回整个完全二叉树的根结点

【思路】

由于题目中二叉树的存储方式是不存储「父结点」的二叉链表形式，那么此时插入一个结点的话，需要遍历整颗二叉树后寻找其父结点，代价过大。然而完全二叉树还可以使用「数组」以层序遍历的顺序存储，这个可通过索引快速的定位「父结点」。

一维数组从 $0$ 开始，当结点的索引为 $i$ 时，其父结点的索引为 $⌈\frac{i-1}{2} ⌉$ ，其左子结点的索引为 $2×i+1$ ，右子结点的索引为 $2×i+2$ 。

【步骤】

将以二叉链表存储的完全二叉树转换为数组存储，存储顺序为层序遍历，也即对树进行「广度优先遍历」的同时存入数组。
插入结点时，直接插入数组末尾即可，然后通过索引寻找「父结点」

代码实现

class CBTInserter {
private:
    TreeNode* root;       // 完全二叉树的根结点
    vector<TreeNode*> h;  // 以层序遍历存储完全二叉树 
public:
  	// BFS 
    CBTInserter(TreeNode* root) {
        this->root = root;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            h.push_back(node);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    int insert(int val) {
        auto t = new TreeNode(val);
        h.push_back(t);
        int k = h.size() - 1;
        int p = (k - 1) / 2;         // 父结点索引 
        // 判断当前结点是左子结点还是右子结点
        if (p * 2 + 1 == k) h[p]->left = t;
        else h[p]->right = t;
        return h[p]->val;
    }
    TreeNode* get_root() {
        return this->root;
    }
};

515.在每个树行中找最大值open in new window

题目的要求是求解二叉树中每层结点值的最大值，并且使用的二叉链表存储的二叉树，那么可对整颗二叉树进行一次遍历即可，在遍历的同时更新每层的最大值即可，使用「深度优先遍历」或者「宽度优先遍历」都可以。

「DFS」做法：

DFS 每次的操作是向下扩展或者向上回溯，每次的递归操作都伴随着所在层数的改变，由于二叉树的深度未知，所以需要一个 max_depth 在 DFS 的同时记录二叉树的深度，然后每到达一层，就更新这层的最大值。步骤：

处理边界：当所在结点为 null 时，回溯。
DFS 时伴随的操作：更新最大深度 max_depth，更新每层的最大值(第一次新的一层到达时，直接填入)；
扩展分支：因为是二叉树，所以向左扩展，或者向右扩展。

「BFS」做法：

BFS 本身就是层序遍历，每次都是遍历一层，但平时写 BFS，一次循环只遍历一层的一个结点，该层的其他结点还在队列中，所以只需要在每次循环中遍历完队列中所有的结点就可以每次遍历一层结点，然后记录最大值即可。

代码实现

// DFS
class Solution {
public:
  // 第 key 层的 最大值 value
  unordered_map<int, int> hash;
  int max_depth = 0;

  vector<int> largestValues(TreeNode* root) {
    dfs(root, 1);
    vector<int> ans;
    for (int i = 1 ; i <= max_depth ; i++) 
      ans.emplace_back(hash[i]);
    return ans;
  }
  void dfs(TreeNode* root, int d) {
    /* 问题边界 */
    if (!root) return;
    // 更新层数
    max_depth = max(max_depth, d);

    /* 到达每层时，需要的操作 */
    // 第一次到达一层时，直接加入
    if (hash.count(d) == 0) hash[d] = root->val;
    else hash[d] = max(hash[d], root->val); // 再次到达时，更新最大值

    /* 向下扩展 */
    // 遍历左子树
    dfs(root->left, d + 1);
    // 遍历右子树
    dfs(root->right, d + 1);
  }

};
// BFS
class Solution {
public:
  vector<int> largestValues(TreeNode* root) {
    if (root == nullptr) return {};
    queue<TreeNode*> q;
    vector<int> ans;
    q.push(root);
    while(!q.empty()) {
      int level_node_num = q.size();
      int max_val = 1 << 31;
      // 每次遍历完队列里的所有值，也即遍历一层
      for (;level_node_num;level_node_num--) {
        auto t = q.front();
        q.pop();
        max_val = max(t->val, max_val);
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
      }
      ans.emplace_back(max_val);
    }
    return ans;
  }
};

513.找树左下角的值open in new window

题目要求是找树中最底层结点的最左层结点，通过一次遍历即可，「宽度优先遍历」和「深度优先遍历」都可以做到。

「宽度优先遍历」:BFS 是从上至下，从左到右的层序遍历，所以只需在 BFS 的同时记录每一层的最左结点，然后每到下一层，再更新这个最左结点即可。

「深度优先遍历」:DFS 是深度优先，在 DFS 优先遍历左子树，然后到达每层时，更新最左结点即可。

代码实现

// DFS
class Solution {
public:
  int left_node , max_depth;
  int findBottomLeftValue(TreeNode* root) {
    dfs(root, 1);
    return left_node;
  }
  void dfs(TreeNode* root, int depth) {
    if (!root) return;
    // 深度增加时，更新最左结点
    if (depth > max_depth) {
      max_depth = depth;
      left_node = root->val;
    }
    // 先搜左子结点
    dfs(root->left, depth + 1);
    // 再搜右子结点
    dfs(root->right, depth + 1);
  }  
};
// BFS
class Solution {
public:
  int findBottomLeftValue(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int left_node = 0;
    while (!q.empty()) {
      int level_size = q.size();
      int flag = 1;    // 标记
      for(;level_size ;level_size--) {
        auto t = q.front();
        q.pop();
        if (flag) {   // 每遍历到一层，只用这层的第一个元素(最左结点)更新
          left_node = t->val;
          flag --;
        }
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
      }
    } 
    return left_node;
  }
};

103. 二叉树的锯齿形层序遍历open in new window

题目要求对二叉树奇数深度层进行从左至右的遍历，对偶数层进行从右至左的遍历。可直接使用双端队列：

奇数深度时，队列左出右进
偶数深度时，队列右出左进

代码实现

class Solution {
public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    deque<TreeNode*> q;
    q.push_back(root);
    vector<vector<int>> levels;
    if (!root) return levels;
    bool flag = true;  // 奇数层 == true or 偶数层 == false 
    while(!q.empty()) {
      int level_size = q.size();
      vector<int> cur_level;
      for (;level_size; level_size --) {
        if (flag) { // 奇数层
          auto t = q.front();
          q.pop_front();    // 从左至右
          cur_level.push_back(t->val);
          if (t->left) q.push_back(t->left);
          if (t->right) q.push_back(t->right);
        }else {     // 偶数层
          auto t = q.back();
          q.pop_back();     // 从右至左
          cur_level.push_back(t->val);
          if (t->right) q.push_front(t->right);
          if (t->left) q.push_front(t->left);
        }
      }
      flag = flag == true ? false : true;
      levels.push_back(cur_level);
    }
    return levels;
  }
};