Garden | Tree

二叉树遍历

144. 二叉树的前序遍历

递归写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空节点不入栈）
            if (node->left) st.push(node->left);             // 左（空节点不入栈）
        }
        return result;
    }
};

94. 二叉树的中序遍历

递归写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    void dfs(TreeNode* root, vector<int>& vec) {
        if(!root) return;
        dfs(root -> left, vec);
        vec.push_back(root -> val);
        dfs(root -> right, vec);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        dfs(root, vec);
        return vec;
    }
};

迭代写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        
        if (root == nullptr) return result;

        TreeNode* cur = root;
        while (cur || !stk.empty()) {
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }

            cur = stk.top();
            stk.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }
        return result;
    }
};

145. 二叉树的后序遍历

递归写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
        vec.push_back(cur->val);    // 中
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
    }
};

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


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

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

        while (!q.empty()) {
            vector<int> layer;

            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* cur = q.front();
                q.pop();

                layer.push_back(cur->val);

                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }

            result.push_back(layer);
        }

        return result;
    }
};

103. 二叉树的锯齿形层序遍历

 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


class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if (root == nullptr) return result;

        queue<TreeNode*> q;
        q.push(root);
        bool left2right = true;

        while (!q.empty()) {
            int size = q.size();
            vector<int> layer;

            for (int i = 0; i < size; i++) {
                TreeNode* cur = q.front();
                q.pop();
                layer.push_back(cur->val);

                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }

            if (left2right == false) reverse(layer.begin(), layer.end());
            result.push_back(layer);
            left2right = !left2right;
        }
        return result;

    }
};

987. 二叉树的垂序遍历

二叉树路径问题

112. 路径总和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return false;
        }
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }
        return hasPathSum(root->left, sum - root->val) ||
               hasPathSum(root->right, sum - root->val);
    }
};

113. 路径总和 II

 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


class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> result;

        if (root == nullptr) return result;

        path.push_back(root->val);
        dfs(root, targetSum, path, result);

        return result;
    }

    void dfs(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
        if (root == nullptr) return;

        if (root->left == nullptr && root->right == nullptr) {
            if (root->val == targetSum) {
                result.push_back(path);
            }
            return;
        }


        if (root->left != nullptr) {
            path.push_back(root->left->val);
            dfs(root->left, targetSum-root->val, path, result);
            path.pop_back();
        }

        if (root->right != nullptr) {
            path.push_back(root->right->val);
            dfs(root->right, targetSum-root->val, path, result);
            path.pop_back();
        }
    }
};

437. 路径总和 III

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int ans = 0;

    void dfs(TreeNode* root, long long currSum, int targetSum){
        if (root == nullptr)    return;
        currSum += root->val;
        if (currSum == targetSum) ans++;
        dfs(root->left, currSum, targetSum);
        dfs(root->right, currSum, targetSum);
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr)    return 0;
        dfs(root, 0, targetSum);
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);
        return ans;
    }
};

前缀和思路

 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


class Solution {
public:
    int targetSum;
    int ans = 0;

    void dfs(TreeNode* root, long long currSum, unordered_map<long long, int>& prefix){
        if (root == nullptr)    return;
        currSum += root->val;
      	// 以 当前节点 b 为 终点。
        if (prefix.count(currSum - targetSum)){
          ans += prefix[currSum - targetSum];
        }
        // 以 当前节点 b 为路径的一部分。
        prefix[currSum]++;
        dfs(root->left, currSum, prefix);
        dfs(root->right, currSum, prefix);
      	// 当子树结束时，应当把子树从哈希表中移除 (回溯：将一切复原，然后结束)。
        prefix[currSum]--;
    }

    int pathSum(TreeNode* root, int _targetSum) {
        targetSum = _targetSum;
        unordered_map<long long, int> prefix;  // 类似 Leetcode 1 两数之和
      	// 注意 前缀和中, [a, b] = [0, b] - [0, a-1] 。
        // 对于包含根节点的路径，是无法找到 a-1 的。所以需要一个虚拟根节点。
        prefix[0] = 1;
        dfs(root, 0, prefix);
        return ans;
    }
};

257. 二叉树的所有路径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点
                paths.push_back(path);                              // 把路径加入到答案中
            } else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};

543. 二叉树的直径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

124. 二叉树中的最大路径和

 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


class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

687. 最长同值路径

 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


class Solution {
public:
    int maxLen = 0;
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return maxLen;
    }

    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;

        int left = dfs(root->left);
        if (left > 0 && root->left->val != root->val) {
            left = 0;
        }

        int right = dfs(root->right);
        if (right > 0 && root->right->val != root->val) {
            right = 0;
        }

        maxLen = max(maxLen, left+right);

        return 1 + max(left, right);
    }
};

129. 求根节点到叶节点数字之和

 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


class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (root == nullptr) return 0;

        int result = 0;
        int value = 0;

        dfs(root, value, result);

        return result;
    }

    void dfs(TreeNode* root, int& value, int& result) {
        if (root == nullptr) return;

        value = value * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            result += value;
            value /= 10;
            return;
        }

        dfs(root->left, value, result);
        dfs(root->right, value, result);

        value /= 10;
    }
};

863. 二叉树中所有距离为 K 的结点

 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
45


class Solution {
    unordered_map<int, TreeNode*> parents;
    vector<int> ans;

    void findParents(TreeNode* node) {
        if (node->left != nullptr) {
            parents[node->left->val] = node;
            findParents(node->left);
        }
        if (node->right != nullptr) {
            parents[node->right->val] = node;
            findParents(node->right);
        }
    }

    void findAns(TreeNode* node, TreeNode* from, int depth, int k) {
        if (node == nullptr) {
            return;
        }
        if (depth == k) {
            ans.push_back(node->val);
            return;
        }
        if (node->left != from) {
            findAns(node->left, node, depth + 1, k);
        }
        if (node->right != from) {
            findAns(node->right, node, depth + 1, k);
        }
        if (parents[node->val] != from) {
            findAns(parents[node->val], node, depth + 1, k);
        }
    }

public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        // 从 root 出发 DFS，记录每个结点的父结点
        findParents(root);

        // 从 target 出发 DFS，寻找所有深度为 k 的结点
        findAns(target, nullptr, 0, k);

        return ans;
    }
};

988. 从叶结点开始的最小字符串

二叉树构造

105. 从前序与中序遍历序列构造二叉树

利用 hash table 快速定位根节点

 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


class Solution {
public:
    unordered_map<int, int> index;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_l, int pre_r, int in_l, int in_r) 		 {
        if (pre_l > pre_r) return nullptr;

        int pre_root = pre_l;
        int in_root = index[preorder[pre_root]];

        TreeNode* root = new TreeNode(preorder[pre_root]);

        int size_left = in_root - in_l;
        root->left = build(preorder, inorder, pre_l + 1, pre_l+size_left, in_l, in_root-1);
        root->right = build(preorder, inorder, pre_l+size_left+1, pre_r, in_root+1, in_r);

        return root;
    }
};

106. 从中序与后序遍历序列构造二叉树

 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


class Solution {
public:
    unordered_map<int, int> index;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }

        return build(inorder, postorder, 0, n-1, 0, n-1);
    }

    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int in_l, int in_r, int post_l, int post_r) {
        if (post_l > post_r) return nullptr;

        int post_root = post_r;
        int in_root = index[postorder[post_root]];

        TreeNode* root = new TreeNode(postorder[post_root]);

        int size_l = in_root - in_l;

        root->left = build(inorder, postorder, in_l, in_root-1, post_l, post_l+size_l-1);
        root->right = build(inorder, postorder, in_root+1, in_r,  post_l+size_l, post_root-1);
        return root;
    }
};

889. 根据前序和后序遍历构造二叉树

1028. 从先序遍历还原二叉树

114. 二叉树展开为链表

 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


class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return;

        update(root);
    }

    TreeNode* update(TreeNode *root) {
        if (root == nullptr) return nullptr;

        TreeNode* left = root->left;
        TreeNode* right = root->right;

        TreeNode* newRight = update(left);
        TreeNode* newTail = update(right);

        if (newRight) {
            TreeNode* cur = newRight;
            while (cur->right) cur = cur->right;
            cur->right = newTail;
        } else {
            newRight = newTail;
        }

        root->left = nullptr;
        root->right = newRight;
        return root;
    }
};

109. 有序链表转换二叉搜索树

 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


class Solution {
public:
    ListNode* getMedian(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while (fast != right && fast->next != right) {
            fast = fast->next;
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right) {
        if (left == right) {
            return nullptr;
        }
        ListNode* mid = getMedian(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left = buildTree(left, mid);
        root->right = buildTree(mid->next, right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

108. 将有序数组转换为二叉搜索树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

1008. 前序遍历构造二叉搜索树

二叉树序列化

297. 二叉树的序列化与反序列化

449. 序列化和反序列化二叉搜索树

655. 输出二叉树

606. 根据二叉树创建字符串

求二叉树属性

104. 二叉树的最大深度

111. 二叉树的最小深度

404. 左叶子之和

222. 完全二叉树的节点个数

515. 在每个树行中找最大值

513. 找树左下角的值

662. 二叉树最大宽度

199. 二叉树的右视图

236. 二叉树的最近公共祖先

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || p == root || q == root) return root;
        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
        if (!l && !r) return nullptr;
        if (l && r) return root;
        if (!l) return r;
        if (!r) return l;
        return nullptr;
    }
};

637. 二叉树的层平均值

563. 二叉树的坡度

652. 寻找重复的子树

验证二叉树

100. 相同的树

101. 对称二叉树

110. 平衡二叉树

98. 验证二叉搜索树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        int value = root->val;

        return isValid(root->left, LONG_MIN, value) && isValid(root->right, value, LONG_MAX);
    }

    bool isValid(TreeNode* root, long long minValue, long long maxValue) {
        if (root == nullptr) return true;

        if (root->val <= minValue) return false;
        if (root->val >= maxValue) return false;

        return isValid(root->left, minValue, root->val) && isValid(root->right, root->val, maxValue);
    }
};

958. 二叉树的完全性检验

993. 二叉树的堂兄弟节点

剑指 Offer 26. 树的子结构

二叉树修改

226. 翻转二叉树

617. 合并二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr && root2 == nullptr) return nullptr;
        if (root1 == nullptr) return root2;
        if (root2 == nullptr) return root1;

        root1->val += root2->val;

        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);

        return root1;
    }
};

814. 二叉树剪枝

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

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

919. 完全二叉树插入器

二叉搜索树

96. 不同的二叉搜索树

99. 恢复二叉搜索树

218 The Skyline Problem
- O(nlog(n)) time using line sweeping and map.
220 Contains Duplicate III
- Given a number array, find if there are two elements nums[i] and nums[j] i.e. abs(i-j)<=k and (nums[i]-nums[j])<=t.
- Use set::lower_bound. Enumerate window at size K.
230 Kth Smallest Element in a BST
- Save count in node to keep log(n) query time.
352 Data Stream as Disjoint Intervals
- Given number stream, merge them into intervals.
450 Delete Node in a BST
480 Sliding Window Median
- Use cpp multiset.
938 Range Sum of BST
105 Construct Binary Tree from Preorder and Inorder Traversal
- O(n) time and O(n) space, record val’s inorder index.
106 Construct Binary Tree from Inorder and Postorder Traversal
129 Sum Root to Leaf Numbers
- Each node is a digit, find sum of numbers formed by root-leaf paths.
144 Binary Tree Preorder Traversal
145 Binary Tree Postorder Treversal
- Morris Traversal. Reverse of left-right mirrored pre-order is post-order.
156 Binary Tree Upside Down
- Do the following transformation recursively: (all right nodes are whether leaf with sibling or nullptr)
```
  1      4
 2 3 => 5 2
4 5      3 1
```
173 Binary Search Tree Iterator
- Average O(1) time and O(h) memory for next() and hasNext().
- Can delete visited nodes, since it’s single directional visiting.
250 Count Univalue Subtrees
- Find the number of univalue subtrees, where all nodes are of the same value.
255 Verify Preorder Sequence in Binary Search Tree
- O(n) time by iterative traversal.
- O(1) space by mono-stack and reuse input vector. Mono stack saves nodes not visited yet, thus all nodes less than current value must be visited (popped), because they can only be in left trees.
- Preorder sequence: DDDDIIIDDDDIIIIDDD…, keep a lowest bound for popped ones, they’re left subtrees already visited.
272 Closest Binary Search Tree Value II
- Given a BST and target value, find k nearest neighbor.
- O(klog(n)) time using stack-based iterative traversal.
- Cannot delete visited nodes, because it’s bi-directional visiting.
285 Inorder Successor in BST
297 Serialize and Deserialize Binary Tree
298 Binary Tree Longest Consecutive Sequence
- Given a binary tree, find the length of longest consecutive sequence going from up to down.
- O(n) time, simple tree DP.
314 Binary Tree Vertical Order Traversal
- Given a binary tree, output its vertical order traversal. For example:
```
      2
    3   4    => 1 3 2 5 0 4 6
  1  5|0  6
```
- Traverse the tree and emit (node, position) pairs. O(n) time can be achieved if using hashmap.
337 House Robber III
- Rob on a tree, adjacent nodes cannot be robbed.
- O(n) time, typical tree DP.
366 Find Leaves of Binary Tree
- Remove leaves of a binary tree step by step.
- Tree DP. for each node calculate it’s shortest path to leaf.
426 Convert Binary Search Tree to Sorted Doubly Linked List
- Convert BST to a sorted list, left=prev, right=next.
- Simple divide and conquer.
428 Serialize and Deserialize N-ary Tree
- Simple recursion.
431 Encode N-ary Tree to Binary Tree
- Left-(first) children and right-sibiling.
449 Serialize and Deserialize BST
- Use 1,,-1,,, like preorder traversal string.
545 Boundary of Binary Tree
- Maintain isLeftBound and isRightBound in preorder traversal.
742 Closest Leaf in a Binary Tree
- Find the value of nearest leaf to some target node.
- Save nearest leaf for nodes on the root-to-target path.
- Convert tree to graph.
951 Flip Equivalent Binary Trees
965 Univalued Binary Tree
971 Flip Binary Tree To Match Preorder Traversal
987 Vertical Order Traversal of a Binary Tree
- Similar to 314.
993 Cousins in Binary Tree
- Two nodes are cousins if they are at the same depth but have different parents. Find whether two nodes are cousins.
998 Maximum Binary Tree II
- A maximum tree is whose root is alwasy the largest. Given a number array, a max tree can be constructed by recursively pick maximum and build left/right sub arrays. Now append a new number to origin array, insert the number into the origin maximum tree.

参考资料

https://leetcode.cn/circle/article/632PIi/