树

作为链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有两个子节点；LeetCode 默认的树表示方法如下：

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) {}
};

树的递归

Maximum Depth of Binary Tree

题目：

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

题解：

one-line code

1
2
3
int maxDepth(TreeNode* root) {
    return root? 1 + max(maxDepth(root->left), maxDepth(root->right)): 0;
}

cool！😘

Balanced Binary Tree

题目：

Given a binary tree, determine if it is height-balanced.

题解：

递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 主函数
bool isBalanced(TreeNode* root) {
    return helper(root) != -1;
}
// 辅函数
int helper(TreeNode* root) {
    if (!root)
        return 0;
    int left = helper(root->left), right = helper(root->right);
    if (left == -1 || right == -1 || abs(left - right) > 1)
        return -1;	// 避免重复计算
    return 1 + max(left, right);
}

Diameter of Binary Tree

题目：

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

题解：

递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 主函数
int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    helper(root, diameter);
    return diameter;
}
// 辅函数
int helper(TreeNode* node, int& diameter) {
    if (!node)
        return 0;
    int l = helper(node->left,diameter), r = helper(node->right,diameter);
    diameter = max(l + r, diameter);
    return max(l, r) + 1;
}

Path Sum III

题目：

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

题解：

递归每个节点时，需要分情况考虑：

  • 如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点
  • 如果不选取该节点加入路径，则对其左右节点进行重新进行考虑。
1
2
3
4
5
6
7
8
9
10
11
12
13
// 主函数
int pathSum(TreeNode* root, int sum) {
    return root? pathSumStartWithRoot(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum): 0;
}
// 辅函数
int pathSumStartWithRoot(TreeNode* root, int sum) {
    if (!root)
        return 0;
    int count = root->val == sum? 1: 0;
    count += pathSumStartWithRoot(root->left, sum - root->val);
    count += pathSumStartWithRoot(root->right, sum - root->val);
    return count;
}

Symmetric Tree

题目：

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

题解：

判断两个子树是否相等或对称类型的题的解法叫做“四步法”：

  • 如果两个子树都为空指针，则它们相等或对称
  • 如果两个子树只有一个为空指针，则它们不相等或不对称
  • 如果两个子树根节点的值不相等，则它们不相等或不对称
  • 根据相等或对称要求，进行递归处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 主函数
bool isSymmetric(TreeNode *root) {
    return root? isSymmetric(root->left, root->right): true;
}
// 辅函数
bool isSymmetric(TreeNode* left, TreeNode* right) {
    if (!left && !right)
        return true;
    if (!left || !right)
        return false;
    if (left->val != right->val)
        return false;
    return isSymmetric(left->left,right->right) && isSymmetric(left->right, right->left);
}

Delete Nodes And Return Forest

题目：

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

题解：

这道题最主要需要注意的细节是如果通过递归处理原树，以及需要在什么时候断开指针。同时，为了便于寻找待删除节点，可以建立一个哈希表方便查找。

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<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
    vector<TreeNode*> forest;
    unordered_set<int> dict(to_delete.begin(), to_delete.end());
    root = helper(root, dict, forest);
    if (root)
        forest.push_back(root);
    return forest;
}
// 辅函数
TreeNode* helper(TreeNode* root, unordered_set<int> & dict, vector<TreeNode*> &forest) {
    if (!root)
        return root;
    // 从底往上删
    root->left = helper(root->left, dict, forest);
    root->right = helper(root->right, dict, forest);
    if (dict.count(root->val)) {
        if (root->left)
            forest.push_back(root->left);
        if (root->right)
            forest.push_back(root->right);
        root = NULL;
    }
    return root;
}

层次遍历

Average of Levels in Binary Tree

题目：

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within $10^{-5}$ of the actual answer will be accepted.

题解：

利用广度优先搜索和队列进行层次遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<double> averageOfLevels(TreeNode* root) {
    vector<double> ans;
    if (!root)
        return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int count = q.size();
        double sum = 0;
        for (int i = 0; i < count; ++i) {
            TreeNode* node = q.front();
            q.pop();
            sum += node->val;
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
        ans.push_back(sum / count);
    }
    return ans;
}

前中后序遍历

前序遍历先遍历父结点，再遍历左结点，最后遍历右节点

1
2
3
4
5
void preorder(TreeNode* root) {
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

中序遍历先遍历左节点，再遍历父结点，最后遍历右节点

1
2
3
4
5
void inorder(TreeNode* root) {
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

后序遍历先遍历左节点，再遍历右结点，最后遍历父节点

1
2
3
4
5
void postorder(TreeNode* root) {
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

Construct Binary Tree from Preorder and Inorder Traversal

题目：

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

题解：

前驱遍历结果的第一位为根节点，然后在中序遍历结果中获取左子树长度，然后回到前驱遍历数组得到左右子树的根节点，递归构造左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 主函数
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty())
        return nullptr;
    unordered_map<int, int> hash;
    for (int i = 0; i < inorder.size(); ++i)
        hash[inorder[i]] = i;
    return buildTreeHelper(hash, preorder, 0, inorder.size()-1, 0);
}
// 辅函数
TreeNode* buildTreeHelper(unordered_map<int, int> &hash, vector<int> &preorder, int s0, int e0, int s1) {
    if (s0 > e0)
        return nullptr;
    int mid = preorder[s1], index = hash[mid], leftLen = index - s0 - 1;
    TreeNode* node = new TreeNode(mid);
    node->left = buildTreeHelper(hash, preorder, s0, index-1, s1+1);
    node->right = buildTreeHelper(hash,preorder,index+1,e0,s1+2+leftLen);
    return node;
}

Binary Tree Preorder Traversal

题目：

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

题解：

递归方式前面有，用栈可以写出非递归方式的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (!root)
        return ret;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        ret.push_back(node->val);
        if (node->right)
            s.push(node->right); // 先右后左，保证左子树先遍历
        if (node->left)
            s.push(node->left);
    }
    return ret;
}

二叉查找树

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树：对于每个父节点，其左子树中所有节点的值小于等于父结点的值，其右子树中所有节点的值大于等于父结点的值。因此对于一个二叉查找树，我们可以在 O(log n) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。

一个二叉查找树的实现如下。

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
46
47
48
49
50
51
52
53
54
55
56
57
struct Node {
    T data;
    Node* left;
    Node* right;
};
Node* root;
Node* makeEmpty(Node* t) {
    if (t == NULL) return NULL;
    makeEmpty(t->left);
    makeEmpty(t->right);
    delete t;
    return NULL;
}
Node* insert(Node* t, T x) {
    if (t == NULL) {
        t = new Node;
        t->data = x;
        t->left = t->right = NULL;
    }
    else if (x < t->data)
        t->left = insert(t->left, x);
    else if (x > t->data)
        t->right = insert(t->right, x);
    return t;
}
Node* find(Node* t, T x) {
    if (t == NULL) return NULL;
    if (x < t->data) return find(t->left, x);
    if (x > t->data) return find(t->right, x);
    return t;
}
Node* findMin(Node* t) {
    if (t == NULL || t->left == NULL) return t;
    return findMin(t->left);
}
Node* findMax(Node* t) {
    if (t == NULL || t->right == NULL) return t;
    return findMax(t->right);
}
Node* remove(Node* t, T x) {
    Node* temp;
    if (t == NULL) return NULL;
    else if (x < t->data) t->left = remove(t->left, x);
    else if (x > t->data) t->right = remove(t->right, x);
    else if (t->left && t->right) {
        temp = findMin(t->right);
        t->data = temp->data;
        t->right = remove(t->right, t->data);
    }
    else {
        temp = t;
        if (t->left == NULL) t = t->right;
        else if (t->right == NULL) t = t->left;
        delete temp;
    }
    return t;
}

Recover Binary Search Tree

题目：

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

题解：

我们可以使用中序遍历这个二叉查找树，同时设置一个 prev 指针，记录当前节点中序遍历时的前节点。如果当前节点大于 prev 节点的值，说明需要调整次序。有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换；如果出现了两次次序错误，那就需要交换这两个节点。

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
// 主函数
void recoverTree(TreeNode* root) {
    TreeNode *mistake1 = nullptr, *mistake2 = nullptr, *prev = nullptr;
    inorder(root, mistake1, mistake2, prev);
    if (mistake1 && mistake2) {
        int temp = mistake1->val;
        mistake1->val = mistake2->val;
        mistake2->val = temp;
    }
}
// 辅函数
void inorder(TreeNode* root, TreeNode*& mistake1, TreeNode*& mistake2, TreeNode *& prev) {
    if (!root)
        return;
    if (root->left)
        inorder(root->left, mistake1, mistake2, prev);
    if (prev && root->val < prev->val) {
        if (!mistake1) {
            mistake1 = prev;
            mistake2 = root;
        }
        else mistake2 = root;
    }
    prev = root;
    if (root->right)
        inorder(root->right, mistake1, mistake2, prev);
}

Trim a Binary Search Tree

题目：

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

题解：

利用二叉查找树的大小关系，我们可以很容易地利用递归进行树的处理。

1
2
3
4
5
6
7
8
9
10
11
TreeNode* trimBST(TreeNode* root, int L, int R) {
    if (!root)
        return root;
    if (root->val > R)
        return trimBST(root->left, L, R);
    if (root->val < L)
        return trimBST(root->right, L, R);
    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);
    return root;
}

字典树

字典树（Trie）用于判断字符串是否存在或者是否具有某种字符串前缀。

为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)，近似 O(1)的时间内完成搜索，且额外开销非常小。

Implement Trie (Prefix Tree)

题目：

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

题解：

以下是字典树的典型实现方法。

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
class TrieNode {
    public:
    TrieNode* childNode[26];
    bool isVal;
    TrieNode(): isVal(false) {
        for (int i = 0; i < 26; ++i)
            childNode[i] = nullptr;
    }
};
class Trie {
    TrieNode* root;
    public:
    Trie(): root(new TrieNode()) {}
    // 向字典树插入一个词
    void insert(string word) {
        TrieNode* temp = root;
        for (int i = 0; i < word.size(); ++i) {
            if (!temp->childNode[word[i]-'a'])
                temp->childNode[word[i]-'a'] = new TrieNode();
            temp = temp->childNode[word[i]-'a'];
        }
        temp->isVal = true;
    }
    // 判断字典树里是否有一个词
    bool search(string word) {
        TrieNode* temp = root;
        for (int i = 0; i < word.size(); ++i) {
            if (!temp)
                break;
            temp = temp->childNode[word[i]-'a'];
        }
        return temp? temp->isVal: false;
    }
    // 判断字典树是否有一个以词开始的前缀
    bool startsWith(string prefix) {
        TrieNode* temp = root;
        for (int i = 0; i < prefix.size(); ++i) {
            if (!temp)
                break;
            temp = temp->childNode[prefix[i]-'a'];
        }
        return temp;
    }
};

练习

Invert Binary Tree

题目：

Given the root of a binary tree, invert the tree, and return its root.

题解：

从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

1
2
3
4
5
6
7
8
9
TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr)
        return nullptr;
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

Merge Two Binary Trees

题目：

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

题解：

递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    TreeNode* root = new TreeNode(0);
    if (!root1 && !root2)
        return nullptr;
    else if (!root2)
        return root1;
    else if (!root1)
        return root2;
    root->val = root1->val + root2->val;
    root->left = mergeTrees(root1->left, root2->left);
    root->right = mergeTrees(root1->right, root2->right);
    return root;
}

Subtree of Another Tree

题目：

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values ofsubRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

题解：

递归，需要一个判断树相等的辅函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (isEqual(root, subRoot))
        return true;
    if (!root)
        return false;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
bool isEqual(TreeNode* root1, TreeNode* root2) {
    if (!root1 && !root2)
        return true;
    else if (!(root1 && root2))
        return false;
    if (root1->val != root2->val)
        return false;
    return isEqual(root1->left, root2->left) && isEqual(root1->right, root2->right);
}

Sum of Left Leaves

题目：

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

题解：

为了方便判断是否是左叶子，在辅函数中加入一个参数 isleft

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sumOfLeftLeaves(TreeNode* root) {
    int ans = 0;
    sum(root, &ans, 0);
    return ans;
}
void sum(TreeNode* root, int* ans, bool isleft) {
    if (!root)
        return;
    if (root->left == nullptr && root->right == nullptr && isleft)
        *ans += root->val;
    sum(root->left, ans, 1);
    sum(root->right, ans, 0);
    return;
}

Find Bottom Left Tree Value

题目：

Given the root of a binary tree, return the leftmost value in the last row of the tree.

题解：

使用广度优先搜索遍历每一层的节点。在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findBottomLeftValue(TreeNode* root) {
    int ret;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        if (p->right)
            q.push(p->right);
        if (p->left)
            q.push(p->left);
        ret = p->val;
    }
    return ret;
}

Convert BST to Greater Tree

题目：

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

题解：

使用倒着的中序遍历：right->root->left

1
2
3
4
5
6
7
8
9
10
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
    if (root) {
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
    }
    return root;
}

简洁优雅😍

Lowest Common Ancestor of a Binary Search Tree

题目：

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

题解：

从根节点开始。

  • 如果两个节点值都小于根节点，递归左子树
  • 如果两个节点值都大于根节点，递归右子树
  • 如果一个节点值大于根节点，一个节点值小于根节点，返回
1
2
3
4
5
6
7
8
9
10
11
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (p->val < root->val && q->val < root->val)
            root = root->left;
        else if (p->val > root->val && q->val > root->val)
            root = root->right;
        else
            break;
    }
    return root;
}

Minimum Absolute Difference in BST

题目：

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

题解：

中序遍历

1
2
3
4
5
6
7
8
9
10
11
int ans = INT_MAX, prev = -1;
int getMinimumDifference(TreeNode* root) {
    if (!root)
        return 0;
    getMinimumDifference(root->left);
    if (prev != -1)
        ans = min(ans, root->val - prev);
    prev = root->val;
    getMinimumDifference(root->right);
    return ans;
}

Construct Binary Tree from Preorder and Postorder Traversal

题目：

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

题解：

递归问题是一个起点分别为 x, y 长度为 L 的先序遍历和后续遍历数组，pre[x] 为根，pre[x+1] 为左子树的根，若 pre[x+1] = post[M]，则左子树长度为 M-y+1，起点分别为 x+1, y；pre[x+M-y+2] 为右子树的根，右子树长度为 L-x-M+y-2，起点分别为 x+M-y+2, M+1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
    return help(preorder, postorder, 0, 0, preorder.size());
}
TreeNode* help(vector<int>& preorder, vector<int>& postorder, int x, int y, int L) {
    if (L == 0)
        return nullptr;
    TreeNode* root = new TreeNode(preorder[x]);
    if (L == 1)
        return root;
    int M;
    for (int i = y; i < y + L; ++i) {
        if (postorder[i] == preorder[x+1]) {
            M = i;
            break;
        }
    }
    root->left = help(preorder, postorder, x+1, y, M-y+1);
    root->right = help(preorder, postorder, x+M-y+2, M+1, L-M+y-2);
    return root;
}

Construct Binary Tree from Inorder and Postorder Traversal

题目：

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

题解：

类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return help(inorder, postorder, 0, postorder.size()-1, inorder.size());
}
TreeNode* help(vector<int>& inorder, vector<int>& postorder, int x, int y, int L) {
    if (L == 0)
        return nullptr;
    TreeNode* root = new TreeNode(postorder[y]);
    if (L == 1)
        return root;
    int M;
    for (int i = x; i < x + L; ++i) {
        if (inorder[i] == postorder[y]) {
            M = i;
            break;
        }
    }
    root->right = help(inorder, postorder, M+1, y-1, x+L-M-1);
    root->left = help(inorder, postorder, x, y-x-L+M, M-x);
    return root;
}

Binary Tree Inorder Traversal

题目：

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

题解：

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    help(ans, root);
    return ans;
}
void help(vector<int>& ans, TreeNode* root) {
    if (!root)
        return;
    help(ans, root->left);
    ans.push_back(root->val);
    help(ans, root->right);
}

当然，所有递归都能用栈实现，可以试试

Lowest Common Ancestor of a Binary Tree

题目：

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

题解：

定义辅助函数，判断 p 是否在根为 root 的子树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == p || root == q)
        return root;
    if (help(root->left, p)) {
        if (help(root->right, q))
            return root;
        else
            return lowestCommonAncestor(root->left, p, q);
    }
    else {
        if (help(root->right, q))
            return lowestCommonAncestor(root->right, p, q);
        else
            return root;
    }
}
bool help(TreeNode* root, TreeNode*p) {
    if (root == NULL)
        return false;
    if (root == p)
        return true;
    return help(root->left, p) || help(root->right, p);
}

被官方题解薄纱了。。。

定义辅助函数判断 root 子树中是否包含 p 节点或 q 节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* ans;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) 
        return false;
    bool lson = dfs(root->left, p, q);
    bool rson = dfs(root->right, p, q);
    if ((lson && rson) || ((root == p || root == q) && (lson || rson)))
        ans = root;
    return lson || rson || (root == p || root == q);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    dfs(root, p, q);
    return ans;
}

Convert Sorted List to Binary Search Tree

题目：

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced\ binary search tree.

ascending order: 升序

题解：

链表不好处理，把值复制进数组，找中点创建新节点，递归处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* sortedListToBST(ListNode* head) {
    vector<int> copy;
    while(head) {
        copy.push_back(head->val);
        head = head->next;
    }
    return help(copy, 0, copy.size() - 1);
}
TreeNode* help(vector<int>& value, int x, int y) {
    if (x > y)
        return nullptr;
    int mid = (x + y) / 2;
    TreeNode* root = new TreeNode(value[mid]);
    root->left = help(value, x, mid - 1);
    root->right = help(value, mid + 1, y);
    return root;
}

image-20230117182855623.png

输麻了😭

可以先确定树的结构，再按照中序遍历填充值，优化了速度和空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getLength(ListNode* head) {
    int ret = 0;
    for (; head != nullptr; ++ret, head = head->next);
    return ret;
}
TreeNode* buildTree(ListNode*& head, int left, int right) {
    if (left > right)
        return nullptr;
    int mid = (left + right + 1) / 2;
    TreeNode* root = new TreeNode();
    root->left = buildTree(head, left, mid - 1);
    root->val = head->val;
    head = head->next;
    root->right = buildTree(head, mid + 1, right);
    return root;
}
TreeNode* sortedListToBST(ListNode* head) {
    int length = getLength(head);
    return buildTree(head, 0, length - 1);
}

Increasing Order Search Tree

题目：

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

题解：

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inorder(TreeNode *node, vector<int> &res) {
    if (node == nullptr)
        return;
    inorder(node->left, res);
    res.push_back(node->val);
    inorder(node->right, res);
}
TreeNode *increasingBST(TreeNode *root) {
    vector<int> res;
    inorder(root, res);
    TreeNode *dummyNode = new TreeNode(-1);
    TreeNode *currNode = dummyNode;
    for (int value : res) {
        currNode->right = new TreeNode(value);
        currNode = currNode->right;
    }
    return dummyNode->right;
}

Two Sum IV - Input is a BST

题目：

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

题解：

遍历+哈希表

1
2
3
4
5
6
7
8
9
unordered_set<int> hash;
bool findTarget(TreeNode* root, int k) {
    if (!root)
        return false;
    if (hash.find(k - root->val) != hash.end())
        return true;
    hash.insert(root->val);
    return findTarget(root->left, k) || findTarget(root->right, k);
}

Delete Node in a BST

题目：

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

题解：

分类讨论。

  • 如果 root 小于 key，递归右子树；
  • 如果 root 大于 key，递归左子树；
  • 如果 root 等于 key；
    • 无左右子树，返回 null
    • 无左子树，返回 root->right
    • 无右子树，返回 root->left
    • 将右子树中最小值 successor 替代 root
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
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr)
        return nullptr;
    if (root->val > key) {
        root->left = deleteNode(root->left, key);
        return root;
    }
    if (root->val < key) {
        root->right = deleteNode(root->right, key);
        return root;
    }
    if (root->val == key) {
        if (!root->left && !root->right)
            return nullptr;
        if (!root->right)
            return root->left;
        if (!root->left)
            return root->right;
        TreeNode *successor = root->right;
        while (successor->left)
            successor = successor->left;
        root->right = deleteNode(root->right, successor->val);
        successor->right = root->right;
        successor->left = root->left;
        return successor;
    }
    return root;
}