算法练习-DFS

今天专门来复习+学习一下深度优先遍历算法，做一下oj题目。

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

1.验证二叉搜索树

1.1题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
2
/
1 3
输出: true

示例 2:

输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

来源：https://leetcode-cn.com/problems/validate-binary-search-tree

1.2思路分析

该题最显然的思路就是采用中序遍历递归调用算法，最开始是用的把所有节点值放进数组中，然后再检查数组是否有序，后来发现太占用内存和花费时间了，就改了一下，记录一次上次节点的值last，然后用last和当前遍历的节点比较即可，节约内存和缩小运行时间。

1.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int flag;
long int last ;
void findArray(struct TreeNode* root){
    if(root == NULL){
        return NULL;
    }
    findArray(root->left);
    if(last >= root->val)
        flag = 1;
    last = root->val;
    findArray(root->right);
}
bool isValidBST(struct TreeNode* root){
    last = -2147483649;
    flag = 0;
    findArray(root);
    if(flag == 0)
        return true;
    else return false;
}

//再次优化版本
long int last = -2147483649;
bool isValidBST(struct TreeNode* root){
    if(root != NULL){
        if(!isValidBST1(root->left)){
            return false;
        }
        if(last >= root->val){
            return false;
        }
        last=root->val;
        if(!isValidBST1(root->right)){
            return false;
        }
    }
    return true;
}

2.恢复二叉搜索树

2.1题目描述

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

1
/
3

2

输出: [3,1,null,null,2]

3
/
1

2

示例 2:

输入: [3,1,4,null,null,2]

3
/
1 4
/
2

输出: [2,1,4,null,null,3]

2
/
1 4
/
3

来源：https://leetcode-cn.com/problems/recover-binary-search-tree

2.2思路分析

看到该题也是想到应该中序遍历，二叉排序树中序遍历结果应该是一个递增的数列，我们只需要记住两个错误的节点的指针就好啦，然后将这两个指针中的内容交换，即可恢复出正确的序列值。

2.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int flag;
struct TreeNode* myfirst = NULL;
struct TreeNode* mysecond = NULL;
struct TreeNode* last = NULL;

void recoverTree(struct TreeNode* root) {
    myfirst = NULL;
    mysecond = NULL;
    last = NULL;
    flag = 0;
    midOrder(root);
    int first;
    first = myfirst->val;
    myfirst->val = mysecond->val;
    mysecond->val = first;
    return;
}
void midOrder(struct TreeNode* root)
{
    if (root == NULL)
    return;
    midOrder(root->left);
    if (last!=NULL&&root->val < last->val&&flag == 0){
        flag = 1;
        myfirst = last;
        mysecond = root;
    }
    else if (last!=NULL&&root->val < last->val&&flag == 1){
        flag = 2;
        mysecond = root;
    }
    last = root;
    midOrder(root->right);
}

3.相同的树

3.1题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:

1 1
/ \ /
2 3 2 3

[1,2,3], [1,2,3]

输出: true

示例 2:

输入:

1 1
/ \

2 2

[1,2], [1,null,2]

输出: false

示例 3:

输入: 1 1
/ \ /
2 1 1 2

[1,2,1], [1,1,2]

输出: false

来源：https://leetcode-cn.com/problems/same-tree

3.2思路分析

使用递归算法遍历即可，比较相应的访问到的节点值是否相等，边界问题有点恶心，一定要注意到判断语句的边界问题，本身很简单，但是稍微不注意就错了。

3.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

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

4.二叉树最大深度

4.1题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

/ \

9 20
/
15 7

返回它的最大深度 3 。

来源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

4.2思路分析

很简单，递归遍历即可，设置左右两个值，取最大的返回并加一。

4.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int max(int a,int b){
    if(a>b){
        return a;
    }
    return b;
}
int maxDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    } 
    else {
        int left_height = maxDepth(root->left);
        int right_height = maxDepth(root->right);
        return max(left_height, right_height) + 1;
    }
}

5.从前序与中序遍历序列构造二叉树

5.1题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

/
9 20
/
15 7

来源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

5.2思路分析

先序遍历的顺序是 Root -> Left -> Right，这就能方便的从根开始构造一棵树。
首先，preorder 中的第一个元素一定是树的根，这个根又将 inorder 序列分成了左右两棵子树。现在我们只需要将先序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。

5.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    struct TreeNode* newNode;
    int p = 0;
    int i = 0;
    if (preorder == NULL || inorder == NULL || preorderSize <= 0 || inorderSize <= 0) {
        return NULL;
    }

    newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = preorder[p];
    newNode->left = NULL;
    newNode->right = NULL;

    for (i = 0; i < inorderSize; i++) {
        if (inorder[i] == newNode->val) {
            newNode->left = buildTree(&preorder[p + 1], i, inorder, i);
            newNode->right = buildTree(&preorder[p + i + 1], preorderSize - i - 1, &inorder[i + 1], inorderSize - i - 1);
            break;
        }
    }
    return newNode;
}

6.从中序与后序遍历序列构造二叉树

6.1题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

/
9 20
/
15 7

来源：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

6.2思路

和上面的基本差不多，后序遍历的顺序是 Left -> Right ->Root，这就能方便的从根开始构造一棵树。
首先，postorder中的最后一个元素一定是树的根，这个根又将 inorder 序列分成了左右两棵子树。现在我们只需要将后序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。

6.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    struct TreeNode* newNode;
    int p = postorderSize - 1;
    int i = 0;
    if (postorder == NULL || inorder == NULL || postorderSize <= 0 || inorderSize <= 0) {
        return NULL;
    }

    newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = postorder[p];
    newNode->left = NULL;
    newNode->right = NULL;

    for (i = 0; i < inorderSize ; i++) {
        if (inorder[i] == newNode->val) {
            newNode->right = buildTree(&inorder[i + 1], inorderSize - i - 1,&postorder[i], postorderSize - i - 1);
            newNode->left = buildTree(inorder, i,postorder, i);
            break;
        }
    }
    return newNode;
}

7.将有序数组转换为二叉搜索树

7.1题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

来源：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

7.2思路分析

二叉搜索树就是节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

我们首先要找到根节点，根节点就是数组最中间的值，如果是奇数就取最中间，偶数我们这里选择取中间靠左的位置，直接（left+right）/2即可，然后左边调用left~~mid，右边mid+1~~right，递归调用即可。

7.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* helper(int left,int right,int *nums){
    if(left >= right){
        return NULL;
    }
    int midpos = 0;
    midpos = (left+right)/2;
    struct TreeNode *node = malloc(sizeof(struct TreeNode));
    node->val = nums[midpos];
    node->left = helper(left,midpos,nums);
    node->right = helper(midpos+1,right,nums);

    return node;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    return helper(0,numsSize,nums);
}

8.平衡二叉树

8.1题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

返回 true 。

示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

返回 false 。

来源：https://leetcode-cn.com/problems/balanced-binary-tree/

8.2思路

这个最简单的方法就是不停计算子树的最大深度，如果相差大于1，就不是平衡二叉树。结合前面的查找二叉树的最大深度来写这个代码。

8.3代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a,int b){
    if(a>b){
        return a;
    }
    return b;
}
int maxDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    } 
    else {
        int left_height = maxDepth(root->left);
        int right_height = maxDepth(root->right);
        return max(left_height, right_height) + 1;
    }
}
bool isBalanced(struct TreeNode* root){
    if(root == NULL){
        return true;
    }
    if(abs(maxDepth(root->right)-maxDepth(root->left)) > 1){
        return false;
    }

    return isBalanced(root->left)&&isBalanced(root->right);
}

#算法 #DFS

算法练习-DFS

https://chujian521.github.io/blog/2020/03/05/算法练习-DFS/

作者

Encounter

发布于

2020年3月5日

许可协议

漏洞利用练习:Protostar(V2) 上一篇

算法练习-排序算法下一篇