代码随想录刷题记录 6 - 二叉树（1）

记一下刷到哪了，推：代码随想录

6. 二叉树（1）

总结：非递归写法都比较有意思。
（ 题好多刷不完了！）
（ 原来我在你心里那么微不足道。）

145.二叉树的后序遍历

在非递归遍历时，后序遍历 可以 通过反转 先序遍历（根左右）实现。
先序遍历是根左右，入栈时，先根再右再左，这样答案就是 根 左 右
后序遍历是左右根，入栈时，先根再左再右，答案就是 根 右 左 ，最后反转一下序列就是后序遍历。
题目 “590. N 叉树的后序遍历” 也是。

94.二叉树的中序遍历

非递归遍历：

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>order;
        stack<TreeNode*>stk;
        TreeNode* p = root;
        while(p || !stk.empty()) {
            if(p) {
                stk.push(p);
                p = p->left;              
            }
            else {
                p = stk.top();
                stk.pop();
                order.emplace_back(p->val); 
                p = p->right;
            }
        }
        return order;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

116. 填充每个节点的下一个右侧节点指针

方法1. 层次遍历

使用队列记录每一层，O(n)+O(n)
没看到题目说空间是O(1）

方法2. 递归

除了每层的最后一个箭头指向NULL，一共有两种箭头，一种是左儿子指向右儿子，另一种是右儿子指向本身next的左儿子。

    Node* connect(Node* root) {
        if(root == NULL) return root;
        if(root->left && root->right) {
            root->left->next = root->right;
            if(root->next) (root->right)->next = root->next->left;
            root->left = connect(root->left);
            root->right = connect(root->right);
        }
        return root;       
    }
1
2
3
4
5
6
7
8
9
10

时间：O(1) + O(n)

117. 填充每个节点的下一个右侧节点指针 II

方法1. 多次递归

116 是 root->next 就能把下一层连起来
117 需要 root->next->next->next->next->…………
有的 next 并不能一次 dfs 就存在，于是采用了多次递归的方式，每次都去更新 next
直到所有的 next 都有了。

方法2. 非递归

双重循环，一层一层遍历，用这一层的节点更新下一层的 next.
每层开始的时候，添加一个下一层的头节点，使用指针 pre 指向它，如果当前节点有左儿子，就将 pre->next 指向它，更新 pre，右儿子同理。然后利用 next 走向这一层的下一个节点。
每层遍历完后，将指针指向下一层的头结点的next，也就是下一层的第一个节点。

  Node* connect(Node* root) {
       Node* now = root;
       while(now) {
           Node *t = new Node(0);
           Node *pre = t;
           // cout << "---" << endl;
           while(now) {
               // cout << pre->val << endl;
               if(now->left) {
                   pre->next = now->left;
                   pre = pre->next;
               }
               if(now->right) {
                   pre->next = now->right;
                   pre = pre->next;
               } 
               now = now->next;
           }
           now = t->next;
       }
       return root;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22