二叉树与递归

递归思路

二叉树和递归。

• 二叉树问题的思考方式

• 为什么需要使用递归

• 为什么这种写法一定能算出正确答案

• 计算机如何执行递归

• 另一种递归思路

举例子，计算一个二叉树的最大深度(leetcode 104)，根节点到最远叶子节点的距离。一开始陷入二叉树的细节就不太好写代码了。先思考整棵树和左右子树的关系。

整棵树的最大深度 = max(左子树的最大深度, 右子树的最大深度) + 1

要计算子树的最大深度，和计算整个树的深度这个问题是一样的。

• 原问题：计算整棵树的最大深度

• 子问题：计算左右子树的最大深度

做循环计算，在使用同一份代码，那么这种相似问题，按道理也应该使用同一份代码计算。但这里的子问题需要把计算结果返回给上一级问题。子问题的规模比原问题小，不断向下(递)，但总有尽头，即边界条件，直接返回答案(归)。

为什么这么做是对的？理论依据，数学归纳法证明。

#define MAX(a, b) (((a)>(b)) ? (a) : (b))

int maxDepth(struct TreeNode* root) {

    if (root == NULL)   return 0;
    return MAX(maxDepth(root->left), maxDepth(root->right)) + 1;
}

时间复杂度为 O(n)，空间复杂度也是 O(n) 。return 怎么知道回到那个节点上去的，函数调用，栈帧。

另外一种思路，递归时除了把节点传下去，还可以把递归的层数传下去，同时维护一个全局变量，当层数大于最大值，就更新全局变量。这个思路在一些题目里也常用到。

#define MAX(a, b) (((a)>(b)) ? (a) : (b))

int result;

void dfs(struct TreeNode* root, int count)
{
    if (root == NULL)   return;

    count++;                        /* 递归层数 */
    result = MAX(count, result);    /* 记录最深递归层数 */
    dfs(root->left, count);         /* 理解返回的含义 */
    dfs(root->right, count); 
}

int maxDepth(struct TreeNode* root) 
{
    result = 0;
    dfs(root, 0);
    return result;
}

二叉树递归练习

二叉树最小深度(leetcode 111)

思路：递归遍历二叉树，同时判断是否为子叶，使用一个全局变量记录最小深度。

#define MIN(a, b) (((a)<(b)) ? (a) : (b))

int min;

void dfs(struct TreeNode* root, int count)
{
    if (root == NULL)   return;

    count++;

    if ( root->left == NULL && root->right == NULL)
        min = MIN(min, count);

    dfs(root->left, count);
    dfs(root->right, count);
}

int minDepth(struct TreeNode* root) {
    min = INT_MAX;
    dfs(root, 0);
    return (min == INT_MAX) ? 0 : min; 
}

路径总和 leetcode 112

关于递归函数参数与返回值的思考

int target;

bool dfs(struct TreeNode* root, int sum)
{
    if ( root == NULL)
        return false;
    sum += root->val;
    if ( root->left == NULL && root->right == NULL)
    {
        if ( sum == target )    return true;
        else                    return false;
    }
    return dfs(root->left, sum) || dfs(root->right, sum);
}

bool hasPathSum(struct TreeNode* root, int targetSum) {
    target = targetSum;
    return dfs(root, 0);
}

求根节点到叶节点数字之和 leetcode 129

统计二叉树中好节点的数目 leetcode 1448

思路：传入参数中有一个到当前层的最大值，然后维护一个全局变量记录符合要求的节点数。

int count;
void dfs(struct TreeNode* root, int max)
{
    if (root == NULL)       return;
    
    if (root->val >= max)
    {
        max = root->val;
        count++;
    }

    dfs(root->left, max);
    dfs(root->right, max);
}


int goodNodes(struct TreeNode* root){
    count = 0;
    dfs(root, INT_MIN);
    return count;
}

不使用全局变量？使用 return 返回数量呢？

int dfs(struct TreeNode* root, int max)
{
    if (root == NULL)   return 0;
    int ret = 0;
    if (root->val >= max)
    {
        max = root->val;
        ret = 1;
    }
    max = root->val >= max ? root->val : max;
    return ret + dfs(root->left, max) + dfs(root->right, max);
}

int goodNodes(struct TreeNode* root){
    return dfs(root, INT_MIN);
}

二叉树的垂序遍历 987

二叉树相同

判断相同二叉树(leetcode 100)

判断相同二叉树(leetcode 100)。根节点相同，然后左子树要相同，右子树也要相同。

如何判断根节点相同？节点的值相同的前提条件是两个节点都不是空节点，因此判空在先。如果两个节点都是空节点，那么返回 true 即相同，一个编程技巧，判断空节点时可以使用 p == q 来判断，只有都为 NULL 才相同，其他的地址是不可能相同的。这也是一个比较巧妙的边界条件。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {

    if ( (p==NULL) || (q==NULL) )   return p == q;
    return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

判断对称二叉树 leetcode 101

如何思考？如果在没有上一题的的前提下，是否能想到这一步

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if ( p == NULL || q == NULL )   return p == q;
    return (p->val == q-> val) && isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)   return true;
    return isSameTree(root->left, root->right);
}

判断平衡二叉树

#define MAX(a, b) (((a)>(b)) ? (a) : (b))
#define ABS(x)  (((x)>0) ? (x): (-(x)))

int max_depth(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    int l = max_depth(root->left);
    int r = max_depth(root->right);

    if ( l == -1 || r == -1)
        return -1;

    if (ABS(l-r) <= 1)
        return MAX(max_depth(root->left), max_depth(root->right)) + 1;
    else 
        return -1;
}

bool isBalanced(struct TreeNode* root) {

    if (max_depth(root) == -1)
        return false;
    return true;
}

二叉树的右视图 leetcode 199

#define MAX(a, b) (((a)>(b)) ? (a) : (b))
#define ABS(x)  (((x)>0) ? (x): (-(x)))

int max_depth;
int *result;

void find(struct TreeNode* root, int count)
{
    if (root == NULL)
        return;

    count++;
    
    if (count > max_depth)
    {
        result[max_depth] = root->val;
        max_depth = count;
    }

    find(root->right, count);
    find(root->left, count);
}


int* rightSideView(struct TreeNode* root, int* returnSize) {
    max_depth = 0;
    result = malloc(100*sizeof(int));

    find(root, 0);

    *returnSize = max_depth;
    return result;    
}

验证二叉搜索树

二叉树的遍历。前中后序遍历。

二叉树是不是二叉搜索树：对于一个节点来说，左子树节点值小于，右子树节点值大于。左子树右子树也必须是二叉搜索树。

方法一：前序遍历

区间分割。根据当前的节点值确定区间，然后递归左右子树。

先访问节点值，再递归左右子树的做法就是前序遍历(中左右)

bool dfs(struct TreeNode* root, long long int l, long long int r)
{
    if (root == NULL)
        return true;

    return  (root->val > l && root->val < r) && dfs(root->left, l, root->val) && dfs(root->right, root->val, r);
}

bool isValidBST(struct TreeNode* root) {
    return dfs(root, LLONG_MIN, LLONG_MAX);
}

在 dfs 函数中，return 后面的表达，隐含了先访问根节点，然后遍历左子树，遍历右子树。

时间复杂度为 O(n)， 空间复杂度为 O(n)。

方法二：中序遍历

按照递归左子树，访问节点值，递归右子树这个顺序遍历，这就是中序遍历(左中右)。

二叉搜索树中序遍历的优秀性质：中序遍历访问节点值是严格递增的。

long long int pre = LLONG_MIN;

bool isValidBST(struct TreeNode* root) {
    if (root == NULL)
        return true;
    if (isValidBST(root->left) == false)
        return false;
    if (root->val <= pre )
        return false;
    pre = root->val;
    return isValidBST(root->right);
}

存在的问题：leetcode OJ 可能会在同一个进程里重复调用 isValidBST 函数，但是 pre 变量还没更新。同时使用 3 个测试用例，都只包含一个节点为0，但是第一个用例通过了，后面两个没过。

这个问题在一些题目里也遇到过，全局变量初始化后，运行测试用例会出问题，但是在核心代码里重新初始化就可以了。可以反向推断出 leetcode 的 OJ 是子啊一个进程里重复调用算法函数的。

可以通过 OJ 的实现

long long int pre;

bool dfs(struct TreeNode* root)
{
    if (root == NULL)
        return true;
    if (dfs(root->left) == false)
        return false;
    if (root->val <= pre )
        return false;
    pre = root->val;
    return dfs(root->right);    
}

bool isValidBST(struct TreeNode* root) {
    pre = LLONG_MIN;
    return dfs(root);
}

方法三

前序遍历的思路是把区间向下传递，还有一个思路是把节点的范围往上传。

最近公共祖先

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {

    if ( root == NULL || root == p || root == q )
        return root;
    
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left && right)
        return root;

    if (left)
        return left;

    return right;
}

层序遍历

广度优先搜索。递归从根节点出发一直往下走，层序遍历则是一行行遍历。

如何从根节点出发得到每层的值？

初始化一个 current 数组，把根节点放进去，然后开始循环。

还需要一个 next 数组，遍历 current，把左右儿子都记录到 next 中。遍历 current 的同时，记录节点值，遍历结束后添加答案。

使用两个数组实现。

#define MAX_RESULT  100000

int** result;       /* 保存结果的数组 */
int result_len;     /* 结果个数 */
int *column_size;   /* 每个结果的长度 */

struct TreeNode* current[1000];
int cur_len;
struct TreeNode* next[1000];
int nex_len;

int path[1000] = {0}; /* 单个结果 */
int path_len;       /* 单个结果的长度 */

void save_result(void)
{
    result[result_len] = malloc(path_len * sizeof(int));
    column_size[result_len] = path_len;

    for (int i=0; i<path_len; i++)
        result[result_len][i] = path[i];

    result_len++;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    result = malloc(MAX_RESULT * sizeof(int *));
    result_len = 0;
    column_size = malloc(MAX_RESULT * sizeof(int));

    cur_len = 0;

    if (root != NULL)
        current[cur_len++] = root;

    while ( cur_len != 0)
    {
        path_len = 0;
        nex_len = 0;
        for (int i=0; i<cur_len; i++)
        {
            if ( current[i]->left != NULL)
                next[nex_len++] = current[i]->left;
            if ( current[i]->right != NULL)
                next[nex_len++] = current[i]->right; 
            path[path_len++] = current[i]->val;
        }

        save_result();

        for (int i=0; i<nex_len; i++)
        {
            current[i] = next[i];
        } 

        cur_len = nex_len;
    }

    *returnSize = result_len;
    *returnColumnSizes = column_size;  /* 不是 &column_size */
    return result;
}

两个数组可以合并为一个数组，下一层的节点可以跟在当前层节点后面，这就是队列。

此外还有一题为二叉树的锯齿形层序遍历，和这个题差不多。切入的角度：在保存遍历结果时，反转数组。

类似的 leetcode 513 ，找树左下角的值，思路：返回层序遍历最后一层的第一个元素即可。

二叉树遍历节点

前序遍历的定义就是用递归定义的，二叉树本身也是用递归定义的。关于前中后，指的是中间节点的位置。

void preorder(struct TreeNode* root, int* ret, int* returnSize)
{
    if (root==NULL)
        return;

    ret[*returnSize] = root->val;
    (*returnSize)++;

    preorder(root->left, ret, returnSize);
    preorder(root->right, ret, returnSize);
}


int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    preorder(root, ret, returnSize);
    return ret;
}

后序遍历。

void back_order(struct TreeNode* root, int *size, int *out)
{
    if (root == NULL)
        return;

    back_order(root->left, size, out);
    back_order(root->right, size, out);

    out[(*size)] = root->val;
    (*size) ++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {

    int *ret_array = (int *)malloc(100*sizeof(int));
    *returnSize = 0;

    back_order(root, returnSize, ret_array);
    return ret_array;
}