二叉树递归三部曲详解

二叉树很多题目做法须要应用到递归办法，但往往咱们在做题的时候会陷入递归的循环走不进去，这其实是对递归函数了解不到位造成的景象，上面将别离以 669. 修剪二叉搜寻树 和 108. 将有序数组转换为二叉搜寻树 这两个题目为例详解如何应用递归三部曲轻松拿下二叉树题目，

669. 修剪二叉搜寻树

LeetCode 链接

题目 ：给你二叉搜寻树的根节点 root，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜寻树，使得所有节点的值在[low, high] 中。修剪树不应该扭转保留在树中的元素的绝对构造（即，如果没有被移除，原有的父代子代关系都该当保留）。能够证实，存在惟一的答案。所以后果该当返回修剪好的二叉搜寻树的新的根节点。留神，根节点可能会依据给定的边界产生扭转。

示例 1：

输出：root = [1,0,2], low = 1, high = 2
输入：[1,null,2]

示例 2：

输出：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输入：[3,2,null,1]

思路 ：要疾速了解题意并理清思路，须要对递归三部曲有十分粗浅的了解，上面将从 递归三部曲 的角度登程剖析本题

1. 确定递归函数的参数及意义

   TreeNode traversal(TreeNode root, int low, int high)

2. 参数：参数 root 示意该递归层中须要对以 root 为根节点的树进行操作

• 函数意义：以 root 为根节点的树实现了批改节点的操作
• 函数返回值：以 root 为根节点的树实现批改后返回树头
• 确定终止条件
• 终止条件：当遇到空节点时示意整棵树都遍历结束，返回 null
• 确定单层递归逻辑
• 单层逻辑：

对于本题来说，前序遍历、中序遍历和后序遍历都能够做，上面代码给出的是先序遍历，即先解决头结点，再解决左右子树。

a. root 值小于 low 时，示意整个左子树的值都小于 low，因而返回右孩子；

b. root 值大于 high 时，示意整个右子树的值都大于 high，因而返回左孩子；

c. 将左孩子递归函数返回的树头和右孩子递归函数返回的树头别离与 root 节点建设对应的父子关系

剖析完递归三部曲后，整个解题思路就曾经十分清晰了，上面间接给出代码。

代码：

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {return traversal(root, low, high);
    }

    TreeNode traversal(TreeNode root, int low, int high) {if (root == null) {return root;}
        // 以 root 为头结点的树
        if (root.val < low) {
            // 换头操作，返回右孩子
            return traversal(root.right, low, high);
        }
        // 以 root 为头结点的树
        if (root.val > high) {
            // 换头操作，返回左孩子
            return traversal(root.left, low, high);
        }
    // 建设父子关系
        root.left = traversal(root.left, low, high);
        root.right = traversal(root.right, low, high);

        return root;
    }
};

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

LeetCode 链接

题目：给你一个整数数组 nums，其中元素曾经按 升序 排列，请你将其转换为一棵 高度均衡 二叉搜寻树。

示例 1：

输出：nums = [-10,-3,0,5,9]
输入：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

思路 ：上面将从 递归三部曲 的角度登程剖析本题

1. 确定递归函数的参数及意义

   TreeNode *sortedArrayToBST(vector<int> &nums, int low, int high)

2. 参数：应用上上限别离为 low 和 high 的数组 nums 构建搜寻二叉树 , [) 左闭右开

• 函数意义：在区间中构建 mid 值为头结点的搜寻二叉树
• 函数返回值：构建实现后返回头结点
• 确定终止条件
• 终止条件：low >=high 示意数组曾经没有元素能够参加构建二叉树，返回 null
• 确定单层递归逻辑
• 单层逻辑：

对于本题来说，前序遍历、中序遍历和后序遍历都能够做，上面代码给出的是先序遍历，即先解决头结点，再解决左右子树。

应用 mid 值构建头结点，应用 left 和 right 别离接住左孩子和右孩子递归函数返回的树头，返回头结点

剖析完递归三部曲后，整个解题思路就曾经十分清晰了，上面间接给出代码。

代码：

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {if (nums.empty()) {return nullptr;}
        return sortedArrayToBST(nums, 0, nums.size());
    }
    TreeNode *sortedArrayToBST(vector<int> &nums, int low, int high)
    {if (low >= high)
            return nullptr;
        int mid = (low + high) >> 1;
        TreeNode *treeNode = new TreeNode(nums[mid]);
        TreeNode *left = sortedArrayToBST(nums, low, mid);
        TreeNode *right = sortedArrayToBST(nums, mid + 1, high);
        treeNode->left = left;
        treeNode->right = right;
        return treeNode;
    }
};