AllenY's blog

🧑🏻‍💻🎮🍿🎹🗻

Home Archive Tags About

LeetCode刷题记录（二叉树篇）

2024-09-25 12 min read # LeetCode

LeetCode刷题记录（二叉树篇），个人向。
这部分涉及频繁的指针操作，因此专精C++来做题。

[144]、[145]、[94]

难度：Easy
语言：C++

题目描述就不放了，就是二叉树的前中后序遍历。考察最基本的数据结构了解程度，无难度。这里放几种不同的实现方式。

递归遍历

前序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    res.push_back(cur->val);
    traverse(cur->left, res);
    traverse(cur->right, res);
  }

  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

后序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    traverse(cur->left, res);
    traverse(cur->right, res);
    res.push_back(cur->val);
  }

  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

中序遍历。

class Solution {
 public:
  void traverse(TreeNode* cur, vector<int>& res) {
    if (!cur) {
      return;
    }
    traverse(cur->left, res);
    res.push_back(cur->val);
    traverse(cur->right, res);
  }

  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    traverse(root, res);
    return res;
  }
};

三种遍历的递归写法代码基本一样，改下traverse里面顺序即可。

迭代遍历

前序遍历。使用栈来存放节点。
注意要先入右节点再入左节点，这样左节点会先出栈，才符合前序遍历顺序。

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

后序遍历。和前序遍历类似。
为了满足后续遍历的顺序，我们可以交换左右节点入栈的顺序（即先入左节点再入右节点），最后再把结果反转一下顺序。
这样一来，原本前序遍历为中左右，交换入栈顺序变成中右左，结果反转后变成左右中。

class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (!root) return result;
    st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      result.push_back(cur->val);
      if (cur->left) st.push(cur->left);
      if (cur->right) st.push(cur->right);
    }
    reverse(result.begin(), result.end());
    return result;
  }
};

中序遍历会更麻烦些。在前序遍历中，当前节点访问过就可以丢掉了，但是在中序遍历中我们需要把当前节点先入栈存起来，并尽量的先往左遍历，直到遍历到头再尝试弹栈并往右移动。
注意在后序遍历中，我们通过结果反转的方式巧妙规避了这些问题，但中序遍历就不行了。
在写代码时请注意在空节点是否入栈上达成统一意见（以防止写出bug），本人给出的是空节点不入栈的写法。

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
      if (cur) {
        st.push(cur);
        cur = cur->left;
      } else {
        cur = st.top();
        st.pop();
        result.push_back(cur->val);
        cur = cur->right;
      }
    }
    return result;
  }
};

统一迭代法

在前面的迭代方法中，前中后序的写法都不一样，没有做到像递归遍历一样的稍微改下代码顺序即可。因此，对于非递归的方法，也有统一的写法，可做到稍微改下代码顺序即可更改遍历顺序。
统一迭代法的关键是，利用了空指针来做标记，即访问到的节点后会再跟一个空指针入栈，弹栈时遇到空指针才把后面的节点进行处理（加入结果集）。即一个节点实际上会入栈出栈两次，第一次（入栈不带空指针）代表访问到（仅仅是路过），第二次（入栈后带空指针）才代表要处理该节点。
于是，我们可以很容易得到三种遍历的写法。
前序遍历。

class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
        st.push(cur);
        st.push(nullptr);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

后序遍历。

class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        st.push(cur);
        st.push(nullptr);
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

中序遍历。

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    if (root) st.push(root);
    while (!st.empty()) {
      TreeNode* cur = st.top();
      st.pop();
      if (cur) {
        if (cur->right) st.push(cur->right);
        st.push(cur);
        st.push(nullptr);
        if (cur->left) st.push(cur->left);
      } else {
        result.push_back(st.top()->val);
        st.pop();
      }
    }
    return result;
  }
};

[102] Binary Tree Level Order Traversal

难度：Medium
语言：C++

题目描述。
二叉树的层序遍历，也属于数据结构的基本操作。
层序遍历其实就相当于图论的广度优先搜索。只不过，这道题的返回类型是二维vector，即要求把每一层的节点单独作为一个vector<int>分出来，因此我们在内部嵌套一个循环来专门处理某一层的节点。否则，我们只保留最外层的while循环即可（不关心每层的节点从什么地方开始和结束，即退化到广度优先搜索）。

class Solution {
 public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) {
      return result;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
      int level_width = q.size();
      vector<int> cur_level;
      while (level_width-- > 0) {
        TreeNode* cur = q.front();
        q.pop();
        cur_level.push_back(cur->val);
        if (cur->left) {
          q.push(cur->left);
        }
        if (cur->right) {
          q.push(cur->right);
        }
      }
      result.push_back(cur_level);
    }

    return result;
  }
};

[226] Invert Binary Tree

难度：Easy
语言：C++

题目描述。
之前讲了很多种遍历方法，随便选一种用，遍历的同时交换当前节点的左右儿子即可。这里我选用的是递归前序遍历。
需要注意的是，如果选用的是递归中序遍历，两次traversal都要对cur->left进行，因为左右儿子在中间被交换了。

class Solution {
 public:
  void traversal(TreeNode* cur) {
    if (!cur) {
      return;
    }
    TreeNode* tmp = cur->left;
    cur->left = cur->right;
    cur->right = tmp;
    traversal(cur->left);
    traversal(cur->right);
  }
  TreeNode* invertTree(TreeNode* root) {
    traversal(root);
    return root;
  }
};

[101] Symmetric Tree

难度：Easy
语言：C++

题目描述。
同时遍历根节点的左右子树，遍历的同时进行比较即可。注意左子树的left和右子树的right比较，左子树的right和右子树的left比较。
这里使用的是递归的写法。实际上，用队列或者栈等等也可以有不递归的写法（迭代法）。具体来说，就是把left_cur->left, right_cur->right放进容器中，left_cur->right, right_cur->left放进容器中，然后成对从容器中取元素，进行判断即可。具体可见这篇solution。

class Solution {
 public:
  bool traversal(TreeNode* left_cur, TreeNode* right_cur) {
    if (!left_cur || !right_cur) {
      if (left_cur == right_cur) {
        return true;
      } else {
        return false;
      }
    }

    if (left_cur->val != right_cur->val) {
      return false;
    }

    return traversal(left_cur->left, right_cur->right) &&
           traversal(left_cur->right, right_cur->left);
  }

  bool isSymmetric(TreeNode* root) {
    if (!root) {
      return true;
    }

    return traversal(root->left, root->right);
  }
};

[104] Maximum Depth of Binary Tree

难度：Easy
语言：C++

题目描述。
比较闲就顺手写了非递归层序和递归前序的两种写法。事实上这道题写法应该很多，要做的就只是在遍历的同时记录一下深度即可。在这里的话，我选择在非递归层序遍历时用空指针记录一层的结束，然后直接++max_depth；在递归前序遍历中我选择记录cur_level并看条件更新max_level。

class Solution {
 public:
  int maxDepthLevel(TreeNode* root) {
    if (!root) {
      return 0;
    }

    int max_depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);
    while (!q.empty()) {
      TreeNode* cur = q.front();
      q.pop();
      if (!cur) {
        ++max_depth;
        if (!q.empty()) {
          // Not the last level
          q.push(nullptr);
        }
      } else {
        if (cur->left) {
          q.push(cur->left);
        }
        if (cur->right) {
          q.push(cur->right);
        }
      }
    }
    return max_depth;
  }

  void traversal(TreeNode* cur, int cur_level, int& max_level) {
    if (!cur) {
      return;
    }
    cur_level += 1;
    max_level = cur_level > max_level ? cur_level : max_level;
    traversal(cur->left, cur_level, max_level);
    traversal(cur->right, cur_level, max_level);
  }

  int maxDepth(TreeNode* root) {
    int max_level = 0;
    traversal(root, 0, max_level);
    return max_level;
  }
};

[111] Minimum Depth of Binary Tree

难度：Easy
语言：C++

题目描述。
在104的基础上稍加改动即可。在遍历的时候，遇到当前节点的左右儿子都是空指针，说明遇到叶子节点，就可以尝试更新min_level了。

class Solution {
 public:
  void traversal(TreeNode* cur, int cur_level, int& min_level) {
    if (!cur) {
      return;
    }
    if (!cur->left && !cur->right) {
      min_level = cur_level < min_level ? cur_level : min_level;
    }
    traversal(cur->left, cur_level + 1, min_level);
    traversal(cur->right, cur_level + 1, min_level);
  }

  int minDepth(TreeNode* root) {
    if (!root) {
      return 0;
    }

    int min_level = __INT_MAX__;
    traversal(root, 1, min_level);
    return min_level;
  }
};

[222] Count Complete Tree Nodes

难度：Easy
语言：C++

题目描述。
往下遍历的过程中一定会遇到满二叉树，对于满二叉树可以用2h−12^h - 1的公式快速计算数量。可以用向左遍历和向右遍历的深度是否一致来判断当前子树是否为满二叉树，如不是，则往左右子树继续递归（后序遍历）即可。

class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (!root) {
      return 0;
    }

    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int left_depth = 0;
    int right_depth = 0;
    while (left) {
      left = left->left;
      left_depth += 1;
    }
    while (right) {
      right = right->right;
      right_depth += 1;
    }
    if (left_depth == right_depth) {
      return (2 << left_depth) - 1;
    }

    return countNodes(root->left) + countNodes(root->right) + 1;
  }
};

[110] Balanced Binary Tree

难度：Easy
语言：C++

题目描述。
使用后序遍历获取节点高度，同时使用-1来表示子树不平衡。在遍历的同时比较左右子树的高度，如果高度差值绝对值大于1则返回-1即可。

class Solution {
 public:
  int getHeight(TreeNode* cur) {
    if (!cur) {
      return 0;
    }

    int left_height = getHeight(cur->left);
    if (left_height < 0) {
      return -1;
    }
    int right_height = getHeight(cur->right);
    if (right_height < 0) {
      return -1;
    }

    if (abs(left_height - right_height) > 1) {
      return -1;
    }

    return max(left_height, right_height) + 1;
  }

  bool isBalanced(TreeNode* root) { return getHeight(root) >= 0; }
};
Copyright © 2023-2024 Allen Yuan. All rights reserved. RSS