二叉树遍历

二叉树结构体定义

1
2
3
4
5
6
7
8
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

先序遍历

力扣144题

  • 递归
1
2
3
4
5
6
7
8
9
10
vector<int> order = {};
vector<int> preorderTraversal(TreeNode* root){
  if (root) {
    order.push_back(root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
  }

  return order;
}

  • 非递归

    • 栈实现

    遵循的原则：

    1. 根结点入栈
    2. 栈中弹出 curr 并打印
    3. curr 先右孩子（如果有的话）入栈，再左孩子（如果有的话）入栈
    4. 栈为空时停止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> preorderTraversal(TreeNode* root) {
  stack<TreeNode*> s;
  TreeNode* tmp;
  vector<int> order = {};
  if (root) {
    s.push(root);
    while (!s.empty()) {		//若栈不为空
      tmp = s.top();
      s.pop();
      order.push_back(tmp->val);
      
      if (tmp->right) {
        s.push(tmp->right);
      }

      if (tmp->left) {
        s.push(tmp->left);
      }
    }
  }

  return order;
}

  • 非递归

    • morris实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 vector<int> preorderTraversal(TreeNode* root) {
  TreeNode *curr, *most_right;
  vector<int> morris = {};
  curr = root;
  while (curr) {
    morris.push_back(curr->val);
    if (curr->left){
      most_right = curr->left;
      while (most_right->right && most_right->right != curr) {
        most_right = most_right->right;
      }
      if (!most_right->right) {
        most_right->right = curr;
        curr = curr->left;
      }
      else {
        morris.pop_back();
        most_right->right = nullptr;
        curr = curr->right;
      }
    }
    else {
      curr = curr->right;
    }
  }

  return morris;
}

中序遍历

力扣 94 题

  • 递归
1
2
3
4
5
6
7
8
9
10
vector<int> order = {};
vector<int> inorderTraversal(TreeNode* root) {
  if (node) {
    inorderTraversal(node->left);
    order.push_back(node->val);
    inorderTraversal(node->right);
  }

  return order;
}

  • 非递归

    • 栈实现

    遵循原则：

    1. 子树整条左边界，依次入栈，一直到没有左孩子，进入阶段 2
    2. 栈中弹出 curr 并打印，curr 的右子树重复阶段 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> inorderTraversal(TreeNode* root) {
  stack<TreeNode*> s;
  TreeNode* node = root;
  vector<int> order = {};
  while (node || !s.empty()) {
    if (node) {
      s.push(node);
      node = node->left;
    }
    else {
      node = s.top();
      s.pop();
      order.push_back(node->val);
      node = node->right;
    }
  }

  return order;
}

  • 非递归

    • morris实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> morrisIn(TreeNode* root)  {
  TreeNode* curr, * most_right;
  vector<int> order;
  curr = root;
  while (curr) {
    if (curr->left) {
      most_right = curr->left;
      while (most_right->right && most_right->right != curr)
        most_right = most_right->right;
      if (!most_right->right) {
        most_right->right = curr;
        curr = curr->left;
      } else {
        most_right->right = nullptr;
        order.push_back(curr->val);
        curr = curr->right;
      }
    } else {
      order.push_back(curr->val);
      curr = curr->right;
    }
  }

  return order;
}

后序遍历

力扣 145 题

  • 递归
1
2
3
4
5
6
7
8
9
10
11
vector<int> order = {};

vector<int> preorderTraversal(TreeNode* root){
  if (root) {
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    order.push_back(root->val);
  }

  return order;
}

  • 非递归

    • 栈实现

第一种方法，用两个栈

遵循的原则：

  1. 根节点入栈 s1
  2. s1 弹出 curr，压入 s2，curr 的左右孩子（如果有的话）依次入栈s1，一直到 s1 中的元素完全弹出
  3. s2 依次出栈并打印，一直到 s2 中的元素完全弹出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> postorderTraversal(TreeNode* root) {
  stack<TreeNode*> s1;
  stack<TreeNode*> s2;
  TreeNode* node;
  vector<int> order = {};
  if (! root) {
    return order;
  }
  s1.push(root);
  while (!s1.empty()) {
    node = s1.top();
    s2.push(node);
    s1.pop();
    if (node->left) {
      s1.push(node->left);
    }
    if (node->right) {
      s1.push(node->right);
    }
  }

  while (!s2.empty()) {
    order.push_back(s2.top()->val);
    s2.pop();
  }

  return order;
}

第二种方法，用一个栈。这种方法有一个好处，每次访问一个结点（即执行 order.push_back）时，栈中的元素恰好是该结点的祖先。因此如果要打印叶子结点的祖先，或者输出根到叶子的路径，都和这个非递归的后续遍历有关。

遵循的原则：

  1. 子树整条左边界，依次入栈，一直到没有左孩子，进入阶段 2
  2. 栈中弹出 curr，若 curr 的右孩子存在，且右孩子没有被访问过，右子树重复阶段 1
  3. 若 curr 的右孩子不存在或右孩子被访问过，出栈并打印，标记 curr 为被访问过。令 curr 为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vector<int> postorderTraversal(TreeNode* root) {
  stack<TreeNode*> s;
  TreeNode* r = nullptr, *node = root;
  vector<int> order = {};
  if (!root) {
    return order;
  }
  while (node || !s.empty()) {
    if (node) {
      s.push(node);
      node = node->left;
    }
    else {
      node = s.top();
      if (node->right && node->right != r) {
        node = node->right;
        s.push(node);
        node = node->left;
      }
      else {
        order.push_back(node->val);
        s.pop();
        r = node;
        node = nullptr;
      }
    }
  }
}

二叉树层次遍历

最简单的层次遍历其实就几行代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void levelOrder(TreeNode* root) {
	queue<TreeNode*> q;
	TreeNode* node;

	q.push(root);
	while (!q.empty()) {
		node = q.front();
		q.pop();

		cout << "The num is: " << node->val << endl;

		if (node->left) {
			q.push(node->left);
		}

		if (node->right) {
			q.push(node->right);
		}
	}
}

只不过下面的力扣题要统计每一层的信息，所以加了些东西。

力扣 102 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
vector<vector<int>> levelOrder(TreeNode* root) {
  queue<TreeNode*> q;
  vector<vector<int>> order;
  vector<int> level;
  TreeNode* node = root;
  if (!root) {
    return order;
  }

  q.push(node);
  q.push(nullptr);  // 空指针入栈是为了判断每层是否结束
  while (!q.empty()) {
    node = q.front();
    q.pop();
    if (!node) {
      order.push_back(level);
      level.clear();
      if (q.empty()){
        break;
      }
      q.push(nullptr);
    }
    else {
      level.push_back(node->val);
      if (node->left)
        q.push(node->left);
      if (node->right)
        q.push(node->right);
    }
  }
  return order;
}

层次遍历还可用于求二叉树的深度和宽度。 求宽度的话，需要知道每一层有多少个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int treeWidth(TreeNode* root) {
  queue<TreeNode*> q;
  int max_width = 0; // 宽度
  int level_width = 0; // 每一层的宽度
  TreeNode* node = root;

  if (!node) {
      return max_width;
  }

  q.push(node);
  q.push(nullptr);
  while (!q.empty()) {
    node = q.front();
    q.pop();
    if (!node) {    // 一层结束
      max_width = max(max_width, level_width);
      level_width = 0;
      if (q.empty()){
          break;
      }
      q.push(nullptr);
    }
    else {
      level_width++;
      if (node->left)
          q.push(node->left);
      if (node->right)
          q.push(node->right);
    }
  }

  return max_width;
}

二叉树的相关概念及其实现判断

判断是否是搜索二叉树

力扣98

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct TreeInfo {
  bool isBST;
  int maxVal;
  int minVal;
  TreeInfo(bool a, int b, int c) : isBST(a), maxVal(b), minVal(c) {}
};

TreeInfo* process(TreeNode* p) {
  if (not p) {
    return nullptr;
  }

  TreeInfo* leftData = process(p->left);
  TreeInfo* rightData = process(p->right);

  int minVal = p->val;
  int maxVal = p->val;

  if (leftData) {
    minVal = min(minVal, leftData->minVal);
    maxVal = max(maxVal, leftData->maxVal);
  }

  if (rightData) {
    minVal = min(minVal, rightData->minVal);
    maxVal = max(maxVal, rightData->maxVal);
  }

  bool isBST = false;

  if (
    leftData ? (leftData->isBST && leftData->maxVal < p->val) : true
    &&
    rightData ? (rightData->isBST && rightData->minVal > p->val) : true
    ) {

    isBST = true;
  }

  return new TreeInfo(isBST, minVal, maxVal);
}

上题也是关于树的题型的模板。二叉树的递归套路可以解决所有树型DP的问题。

判断是否是满二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct TreeInfo {
  int nodes;
  int height;
  TreeInfo(int a, int b) : nodes(a), height(b) {}
};

TreeInfo* process(TreeNode* p) {
  if (not p) {
    return new TreeInfo(0,0);
  }

  TreeInfo* leftData = process(p->left);
  TreeInfo* rightData = process(p->right);

  // 总结点数：左孩子的结点数 + 右孩子的结点数 + 自己
  int nodes = leftData->nodes + rightData->nodes + 1;
  // 总高度：左孩子与右孩子高度的最大值 + 自己所在的那一层的高度
  int height = max(leftData->height, rightData->height) + 1;

  return new TreeInfo(nodes, height);
}

boolean isFull(TreeNode *head) {
  TreeInfo* tree = process(head);
  int n = tree->nodes;
  int h = tree->height;

  return n == ((1 << height) - 1);
}

判断是否是平衡二叉树

力扣110

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct TreeInfo {
  bool is_balance;
  int height;
  TreeInfo(bool a, int b) : is_balance(a), height(b) {}
};

TreeInfo* process(TreeNode* p) {
  if (not p) {
    return new TreeInfo(false, 0);
  }

  TreeInfo* leftData = process(p->left);
  TreeInfo* rightData = process(p->right);

  bool is_balance = false;
  int height = max(leftData->height, rightData->height) + 1;
  if(
    leftData->is_balance && rightData->is_balance && abs(leftData->height - rightData->height) < 2
  ){
    is_balance = true;
  }

  return new TreeInfo(is_balance, height);
}

boolean isBalance(TreeNode *head) {
  TreeInfo* tree = process(head);
  int n = tree->nodes;
  int h = tree->height;

  return n == ((1 << height) - 1);
}

最近公共祖先问题

力扣236

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  if(root == nullptr || root == p || root == q){
    return root;
  }

  TreeNode *left = lowestCommonAncestor(root->left, p, q);
  TreeNode *right = lowestCommonAncestor(root->right, p, q);

  if(left && right){
    return root;
  }
  
  // 返回存在的那个，或者空
  return left ? left : right;
}

判断是否是完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
boolean isCBT(TreeNode* root) {
  queue<TreeNode*> q;
  TreeNode* node = root;

  TreeNode* left = nullptr;
  TreeNode* right = nullptr;
  // 是否遇到过左右孩子不双全的结点
  boolean isMeet = false;

  if (!root) {
    return true;
  }

  q.push(node);
  q.push(nullptr);  // 空指针入栈是为了判断每层是否结束
  while (!q.empty()) {
    node = q.front();
    q.pop();

    left = node->left;
    right = node->right;

    if(
      // 遇到不双全的结点以后，又发现当前结点不是叶结点
      (isMeet && (left && right))
      ||
      (!left && right)  // 左孩子不存在，但右孩子存在
    ){
      return false;
    }

    if(left){
      q.push(left);
    }

    if(right){
      q.push(right);
    }

    if(!left || !right){
      isMeet = true;
    }
  }
}

二叉树的后继

后继：中序遍历序列中，node 的下一个结点叫作 node 的后继结点。

有没有一种策略在不进行中序遍历的情况下，找到某个结点的后继？

新结构体定义如下：

1
2
3
4
5
6
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode *parent;
};

注意，该结构体新增了一个指向父结点的指针，并不是线索二叉树（线索二叉树利用的是树种的空指针作线索）。

分析：

如果一个结点有右子树，那么它的后继一定是自己右子树上的最左孩子结点。

如果一个结点没有右子树，那么一直往它的父结点寻找，直到它的一个祖先结点是某个结点的左孩子，则这个“某个结点”即为后继。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
TreeNode* getSuccessorNode(TreeNode *node){
  TreeNode* ancesstor;

  if(not node){
    return node;
  }

  if(node.right){
    return getLeftMost(node);
  }

  ancesstor = node->parent;
  while(ancesstor && ancesstor->left != node){
    node = ancesstor;
    ancesstor = ancesstor->parent;
  }

  return ancesstor;
}


TreeNode* getLeftMost(node){
  if(not node){
    return nullptr;
  }

  while(node->left){
    node = node->left
  }
  
  return node;
}

二叉树的序列化和反序列化

即，深度优先（DFS）和宽度优先（BFS）遍历

序列化：内存里的一棵树如何变成字符串形式？

反序列化：如何从字符串形式变成内存里的树？

先序方式的序列化：

1
2
3
4
5
6
7
8
9
10
11
12
13
string serialByPre(TreeNode* head){
  if(!head){
    return "#_";
  }

  string res = to_string(head->val) + "_";

  res += serialByPre(head->left);
  res += serialByPre(head->right);

  return res;

}

按照先序方式进行序列化，反序列化也要按照先序的方式进行

首先补充一个字符串分割函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<string> Stringsplit(const string& str, const char split){

  vector<string> res = {};

  if (str == ""){
    return;
  }		

  //在字符串末尾也加入分隔符，方便截取最后一段
  string strs = str + split;
  size_t pos = strs.find(split);
 
  // 若找不到内容则字符串搜索函数返回 npos
  while (pos != strs.npos){
    string temp = strs.substr(0, pos);
    res.push_back(temp);
    //去掉已分割的字符串,在剩下的字符串中进行分割
    strs = strs.substr(pos + 1, strs.size());
    pos = strs.find(split);
    }

  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
TreeNode* reconByPreString(string preStr){
  queue<string> queue;
  vector<string> values = Stringsplit(preStr, "_");

  for(int i = 0; i < values.size(); i++){
    queue.push(values[i]);
  }

  return reconPreOrder(queue);
}

TreeNode* reconPreOrder(queue<string>& queue){
  string value = queue.front();
  queue.pop();

  if(value == "#"){
    return nullptr;
  }

  TreeNode* head = new TreeNode(atoi(value));
  head->left = reconPreOrder(queue);
  head->right = reconPreOrder(queue);

  return head;
}

序列化的应用：如何判断一棵二叉树是不是另一棵二叉树的子树？

最优解：把树T1和子树T2都序列化，如果T1包含T2的子串(KMP算法)，则T1包含T2。

力扣 572

折纸问题

图

自己定义图结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 边的定义 */
struct Edge{
  int weight;
  Node* from;
  Node* to;

  Edge(int w, Node* f, Node* t) : weight(w), from(f), to(t) {}
};

/* 结点的定义 */
struct Node{
  int value;         // 结点的值
  int in;            // 入度
  int out;           // 出度
  list<Node> nexts;  // 直接邻居有哪些
  list<Edge> edges;  // 边

  Node(int val) : value(val), in(0), out(0) {}
  Node(int val, int i, int o, list<Node> n, list<Edge> e) : value(val), in(i), out(o), nexts(n), edges(e) {}
};

/* 图的定义 */
struct Graph{
  unordered_map<int, Node> nodes;
  unordered_set<Edge> edges;
};