树结构是数据结构中常常出现的，且用到非常多的一种数据结构。树结构中常见的有二叉树，二叉搜索树，AVL树以及B树等。树结构一般可以用递归去求解，如二叉树的遍历算法中，有先序，中序和后续遍历，一般的树结构的遍历中，有DFS（深度优先遍历）和BFS（宽度优先遍历）等都是用递归来实现。今天的实例中，有用递归直接实现的，也有用递归间接实现的。具体问题要具体分析，下面将要介绍几种具体的方法。
实例1：判断一颗二叉树是否是一个有效的二叉搜索树？
浅析：根据二叉搜索树的递归定义，其每个节点的左子树都要比当前节点小，其右子树都要比当前节点大。一个直观的想法是：1、首先判断根节点是否满足要求，如果不满足，直接返回false，程序停止；2、再递归判断左子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算；3、再递归判断右子树是否满足要求，如果不满足，则程序返回false，依次退栈退出计算。但仔细分析发现这个思路有缺陷，不能保证右子树的最小节点比根节点要大，或者左子树的最大节点比根节点要小。这道题可以先用中序遍历（可以用递归）的方式将结果存起来，因为二叉搜索树的中序遍历结果是有序的。通过检查中序遍历结果的有序性即可判断是否为二叉搜索树。
实例2：二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
浅析：首先判断当前节点的值，如果比low要小，说明左子树都要比low小，直接递归调用右子树即可。反之如果比high值要大，则递归调用左子树。如果在low和hight之间（假设其值为val），则，左子树上，递归调用trim[low,val]或trim[low,high],右子树上递归调用trim[low,high],或trim[val, high]。
实例3：给定二叉树的根节点root ，返回所有左叶子之和。
浅析：比较容易判断是否为叶子节点，当为叶子节点时，还需要考虑其父节点指向的左孩子是否为当前的叶子节点。递归实现的示例代码如下：
void sumOfLeftLeaves(TreeNode* root, TreeNode* parent, int& sum) {
if(root && !root->left && !root->right){
if(parent->left == root)
{
sum += root->val;
}
}else{
if(root->left){
sumOfLeftLeaves(root->left, root, sum);
}
if(root->right){
sumOfLeftLeaves(root->right, root, sum);
}
}
}实例4：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
浅析：通过递归可以找到要删除的节点，如果节点是叶子节点，则好办。如果不是叶子节点呢，这个时候需要找到该节点的后继节点（successor）进行替换，然后递归调用后继节点的删除操作。由于后继节点一般是右子树的最左边的节点（可能是叶子节点，可能是含有右子树的节点），删除相对比较容易，不会再次出现递归调用。这道题的具体分析可以参考引文中的说明，比较详细。
后续将继续分析更多的树类型的数据结构的不同的问题场景和解题思路。
Reference
Leave a Reply