关于leetcode:二叉树递归三部曲详解

3次阅读

共计 2314 个字符，预计需要花费 6 分钟才能阅读完成。

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

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]

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

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

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

参数：参数 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;
    }
};

LeetCode 链接

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

示例 1：

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

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

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

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

参数：应用上上限别离为 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;
    }
};

正文完