BinaryTree
2025-06-28 11:03:26 #算法

递归遍历和迭代遍历

1
2
3
4
// 前序递归核心 - 中序、后序同理！
vec.emplace_back(cur->val);
traversal(cur->left, vec);
traversal(cur->right, vec);
  • 递归的实质即栈，因此亦可用迭代遍历实现前中后序。

前序迭代（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root == nullptr) return result;
        
    st.emplace(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); // 中
        st.pop();
        result.emplace_back(node->val);
        if (node->right) st.emplace(node->right); // 右
        if (node->left) st.emplace(node->left); // 左
    }
    return result;
}

中序迭代（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = root;

    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.emplace(cur);
            cur = cur->left; // 左
        } else {
            cur = st.top();
            st.pop();
            result.emplace_back(cur->val); // 中
            cur = cur->right; // 右
        }
    }

    return result;
}

后序迭代（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root == NULL) return result;
    st.emplace(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.emplace_back(node->val); // 中
        if (node->left) st.emplace(node->left); // 左
        if (node->right) st.emplace(node->right); // 右
    }
    // 中右左 -> 左中右
    reverse(result.begin(), result.end());
    return result;
}

从中序和后序遍历序列构造二叉树

  1. 若数组大小为零，说明是空节点。
  2. 若非空，则取后续数组最后一个元素作为节点元素。
  3. 找到后序数组最后一个元素在中序数组的位置，作为切割点。
  4. 切割中序数组，切成中序左数组和中序右数组。
  5. 切割后序数组，切成后序左数组和后序右数组。
  6. 递归处理左区间和右区间。
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
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
    if (postorder.size() == 0) return nullptr;

    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);

    if (postorder.size() == 1) return root;

    // 找到中序遍历的切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }

    // 切割中序数组
    // [0, delimiterIndex)
    vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
    // [delimiterIndex, end)
    vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());

    // postorder 舍弃末尾元素
    postorder.resize(postorder.size() - 1);

    // 切割后序数组
    // [0, leftInorder.size)
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
    // [leftInorder.size(), end)
    vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

    root->left = traversal(leftInorder, leftPostorder);
    root->right = traversal(rightInorder, rightPostorder);

    return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.size() == 0 || postorder.size() == 0) return nullptr;
    return traversal(inorder, postorder);
}

最大二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 左开右闭区间构建最大二叉树
TreeNode* buildMaxBTree(vector<int>& nums, int left, int right) {
    if (left >= right) return nullptr;

    // nums中的最大值
    int maxValueIndex = left;
    for (int k = left + 1; k < right; ++k)
        maxValueIndex = nums[k] > nums[maxValueIndex] ? k : maxValueIndex;
        
    TreeNode* root = new TreeNode(nums[maxValueIndex]);

    // 构建左子树
    root->left = buildMaxBTree(nums, left, maxValueIndex);

    // 构建右子树
    root->right = buildMaxBTree(nums, maxValueIndex + 1, right);

    return root;
}

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    return buildMaxBTree(nums, 0, nums.size());
}

二叉搜索树中的众数

题中所说的众数可能并不唯一，因此要用count和maxCount来结合二叉搜索树的特性搜索众数。

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
vector<int> findMode(TreeNode* root) {
    int maxCount = 0; // 最大频率
    int count = 0;    // 统计频率
    TreeNode* pre = nullptr;
    TreeNode* cur = root;
    vector<int> result;
    stack<TreeNode*> st;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.emplace(cur);
            cur = cur->left;
        } else {
            cur = st.top();
            st.pop();
            if (pre == nullptr)
                count = 1;
            else if (cur->val == pre->val)
                count++;
            else
                count = 1;
                
            if (count == maxCount)
                result.emplace_back(cur->val);
                
            if (count > maxCount) { // 更新最大频率
                maxCount = count;
                result.clear();
                result.emplace_back(cur->val);
            }
            pre = cur;
            cur = cur->right;
        }
    }

    return result;
}

二叉树的最近公共祖先

求最小公共祖先，需要从底向上遍历（后序遍历）

1
2
3
4
5
6
7
8
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == p || root == q || root == nullptr) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左
    TreeNode* right = lowestCommonAncestor(root->right, p, q); // 右
    if (left != nullptr && right != nullptr) return root;
    if (left == nullptr) return right;
    return left;
}

二叉搜索树的插入操作

利用二叉搜索树的特点，当前节点的值大于待插入元素的值就向左遍历，否则向右遍历！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) {
        TreeNode* node = new TreeNode(val);
        return node;
    }
    TreeNode* cur = root;
    TreeNode* parent = root; // 记录上一节点
    while (cur != nullptr) {
        parent = cur;
        if (cur->val > val)
            cur = cur->left;
        else
            cur = cur->right;
    }
    TreeNode* node = new TreeNode(val);
    if (val < parent->val)
        parent->left = node;
    else
        parent->right = node;
    return root;
}

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

本质即找分割点，递归左、右区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* traversal(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 = traversal(nums, left, mid - 1);
    root->right = traversal(nums, mid + 1, right);
    return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = traversal(nums, 0, nums.size() - 1);
    return root;
}

把二叉搜索树转换为累加树

二叉搜索树中序是从小打大，因此右中左是从大到小，利用这一特性！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* convertBST(TreeNode* root) {
    // 二叉搜索树中序是从小到大 右中左则是从大到小
    stack<TreeNode*> st;
    TreeNode* cur = root;
    int pre = 0;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.emplace(cur);
            cur = cur->right; // 右
        } else {
            cur = st.top(); // 中
            st.pop();
            cur->val += pre;
            pre = cur->val;
            cur = cur->left; // 左
        }
    }

    return root;
}
Prev
2025-06-28 11:03:26 #算法
Next