二叉搜索树区间求和的递归与迭代解法

"二叉搜索树的范围求和问题，提供了两种解法，分别是C语言的递归遍历和C++的借助栈迭代遍历。" 在计算机科学中，二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，其每个节点的值满足以下特性： 1. 左子树上所有节点的值均小于当前节点的值。 2. 右子树上所有节点的值均大于当前节点的值。 在给定的问题中，我们被要求找到一个二叉搜索树中值在[L, R]（包括L和R）范围内的所有节点的和。由于二叉搜索树的特性，我们可以有效地进行范围求和操作。 方法一：C语言递归遍历 这个方法基于二叉搜索树的性质，通过递归的方式实现先序遍历。先序遍历的顺序是：根节点 -> 左子树 -> 右子树。在遍历过程中，如果当前节点的值在[L, R]范围内，则累加到结果中。对于不在范围内的节点，根据其值与范围的关系，递归地访问左子树或右子树。具体实现如下： ```c void __preOrderTravel(struct TreeNode* node, int L, int R) { if (node == NULL) return; if (node->val < L) { __preOrderTravel(node->right, L, R); } else if (node->val > R) { __preOrderTravel(node->left, L, R); } else { ret_val += node->val; __preOrderTravel(node->left, L, R); __preOrderTravel(node->right, L, R); } } ``` 方法二：C++借助栈迭代遍历 迭代法主要利用了栈来模拟递归的过程，依然遵循先序遍历的顺序。首先将根节点压入栈中，然后在循环中不断处理栈顶元素，判断其值是否在[L, R]范围内。如果是，累加到结果中；若值小于L，将右子节点压入栈；若值大于R，将左子节点压入栈。代码如下： ```cpp void preOrderTravel(TreeNode* root, int L, int R, int& ret_val) { stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node == NULL) continue; if (node->val < L) { s.push(node->right); } else if (node->val > R) { s.push(node->left); } else { ret_val += node->val; s.push(node->left); s.push(node->right); } } } ``` 这两种方法都能有效地解决二叉搜索树中特定范围节点的求和问题，且时间复杂度都是O(n)，n为树中的节点数。在实际应用中，迭代法通常比递归法更节省内存，因为它避免了函数调用的开销。然而，递归法的代码可能更简洁易懂。