todo:实现Morris遍历

image.png

思路1：栈式DFS

  • 维护两个结构sequence_preorder和stack_nodes，在弹栈的时候插入序列
  • 后入栈的先弹栈，那么后入栈的先插入序列，所以左边的后入栈，右边的先入栈。
  • 需要脑子里面有入栈弹栈的整个流程。结合代码适当记忆。

代码1：

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  21. class Solution {
  22. public:
  23.     vector<int> preorder(Node* root) {
  24.         stack<Node*> stack_nodes;
  25.         vector<int> sequence_preorder;
  26.         if (root == nullptr) {
  27.             return sequence_preorder;
  28.         }
  30.         stack_nodes.push(root);
  31.         while (!stack_nodes.empty()) {
  32.             Node* node_cur = stack_nodes.top();
  33.             stack_nodes.pop();
  34.             sequence_preorder.push_back(node_cur->val);
  35.             for (int i = node_cur->children.size() - 1; i >= 0; --i) {
  36.                 stack_nodes.push(node_cur->children[i]);
  37.             }
  38.         }
  40.         return sequence_preorder;
  42.     }
  43. };