Question brushing plan - depth first search DFS (I)

Interview questions 13. The range of motion of the robot ( secondary )

subject ：

There is one on the ground m That's ok n Grid of columns , From coordinates [0,0] To coordinates [m-1,n-1] . A robot from coordinates [0, 0] The grid starts to move , It can go left every time 、 Right 、 On 、 Move down one space （ Can't move out of the box ）, The sum of the digits of row coordinates and column coordinates is greater than k Lattice of . for example , When k by 18 when , Robots can enter the grid [35, 37] , because 3+5+3+7=18. But it can't get into the grid [35, 38], because 3+5+3+8=19. How many squares can the robot reach ？

 Example  1：

 Input ：m = 2, n = 3, k = 1
 Output ：3
 Example  2：

 Input ：m = 3, n = 1, k = 0
 Output ：1
 Tips ：

1 <= n,m <= 100
0 <= k <= 20

First, analyze the meaning of the question , The robot coordinates from **[0][0]** The position begins , You can move up, down, left and right , When the sum of digits of row coordinates and column coordinates is greater than the number K, It means that the robot can reach .

Generally speaking , The robot can be located in “ Map ” Use a two-dimensional array to represent . Obviously , For digits in a two-dimensional array , It shows a trend of diagonal distribution .

Therefore, the robot can be pushed through the right and left Inquire about You can access all reachable solutions .

This question has BFS, DFS, Dynamic programming And other solutions .

about DFS for , Its essence can be through recursive To find the final solution .

class Solution {
    
private:
	//  Use one 100*100 Of  “ Map ”
    int _map[100][100];
public:
    int movingCount(int m, int n, int k) {
    
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                _map[i][j] = 0;
        return DFS(m, n, 0, 0, k);
    }

    int DFS(int m, int n, int x, int y, int &k){
    
    	// _map[x][y] by 1 This indicates that this node has been traversed , There's no need to double count 
    	// x < 0 y > 0  It's all about boundaries , Once beyond the map boundary, the robot cannot reach 
    	//  Because the map given by the title is  m*n,  therefore m And n It also belongs to the map boundary 
    	// (x / 10 + x % 10 + y / 10 + y % 10) > k  Judge whether the sum of digits in this position is greater than k
        if(_map[x][y] == 1 || x < 0 || y < 0 || x >= m || y >= n ||  (x / 10 + x % 10 + y / 10 + y % 10) > k){
    
            return 0;
        }

		//  If it is normal, it indicates that the position is reachable , Mark the location as 1, Indicates that you can reach and have reached 
        _map[x][y] = 1;

        return DFS(m, n, x+1, y, k) + DFS(m, n, x, y+1, k) + 1;
    }
};

113. The sum of the paths II ( secondary )

subject ：

Given a binary tree and a target and , Find all paths from the root node to the leaf node whose total path is equal to the given target and .

explain : A leaf node is a node that has no children .

 Example :
 Given the following binary tree , And goals and  sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
 return :

[
   [5,4,11,2],
   [5,8,4,5]
]

Same as traversal of binary tree , For the path problem of binary tree, we also need to traverse the whole binary tree .

In this question , If the required path sum is sum Of route , Several conditions must be satisfied ：

• The end of the path must be a leaf node , That is to say root->left == nullptr && root->right == nullptr;
• The sum of paths must be equal to sum, That is to say pathSum == sum;

Only when these two conditions are met is an effective path .

It should be noted that , After using a node , Move the node from path Pop up in , That means that all possible paths through the node have been traversed

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
private:
	// res  Store valid paths 
    vector<vector<int>> res;
    // path  The node of the storage path 
    vector<int> path;

public:
    void DFS(TreeNode *root, int sum,int &target){
    
        if(!root){
    
            return;
        }
        path.push_back(root->val);
        sum += root->val;

		//  Meet the definition of effective path , Add this path to res in 
        if(!root->left && !root->right && target == sum){
    
            res.push_back(path);
            path.pop_back();
            return;
        }

		//  Traverse the left and right subtrees 
        DFS(root->left, sum, target);
        DFS(root->right, sum, target);

		//  If there is no valid path , The node will pop up in the path 
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
    
        DFS(root, 0, sum);
        return res;
    }
};

Interview questions 54. The second of binary search tree k Big node ( Simple )

subject ：

Given a binary search tree , Please find the first one k Big nodes .

 Example  1:

 Input : root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
 Output : 4
 Example  2:

 Input : root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
 Output : 4
 

 Limit ：

1 ≤ k ≤  Number of binary search tree elements 

An important property of search Binary Tree ： The value of all nodes of the left subtree is less than that of the root node , The value of all nodes of the right subtree is greater than that of the root node .

In this way, through the disguised The first sequence traversal To solve the problem .

The first sequence traversal The traversal order is The left subtree -> The root node -> Right subtree , If you use preorder traversal to traverse binary search tree , There is no doubt that the first node is the smallest element in the tree , In turn increase .

Take advantage of this property , Change the traversal order of preorder traversal to Right subtree -> The root node -> The left subtree , This solves the problem .

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
private:
    vector<int> res;
public:
    void DFS(TreeNode *root, int &k){
    
        if(!root){
    
            return;
        }

        DFS(root->right, k);
        // res[0]  It must be the biggest element , In descending order 
        res.push_back(root->val);
        DFS(root->left, k);
    }

    int kthLargest(TreeNode* root, int k) {
    
        DFS(root, k);

        return res[k-1];
    }
};

In fact, it can be further optimized , There is no need to traverse all nodes in the tree , What we need is k The biggest element , that res.size == k You can guarantee the required results .

Optimized code ：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
private:
    vector<int> res;
public:
    void DFS(TreeNode *root, int &k){
    
        if(!root){
    
            return;
        }

		//  No need to traverse all nodes 
        if(res.size() == k){
    
            return;
        }

        DFS(root->right, k);
        res.push_back(root->val);
        DFS(root->left, k);
    }

    int kthLargest(TreeNode* root, int k) {
    
        DFS(root, k);

        return res[k-1];
    }
};

1302. The sum of the deepest leaf nodes ( secondary )

subject ：

Here is a binary tree for you , Please return the sum of the deepest leaf nodes .

Example ：

 Input ：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
 Output ：15
 

 Tips ：

 The number of nodes in the tree is in  1  To  10^4  Between .
 The value of each node is in  1  To  100  Between .

The key to solving this problem is How to determine the depth of the node And How to determine the maximum depth of binary tree .

Review the maximum depth solution process of binary tree , The most important step in using recursive methods depth = max(leftDepth, rightDepth) + 1; Use similar methods ：

• Each node has a dep Variable to mark the depth of the node , Use sum To record the sum of the deepest leaf nodes in layers ;
• Compare the current node depth with the maximum depth maxDepth
  – if dep > maxDepth , Indicates that the maximum depth needs to be changed , take maxDepth Change for dep, At the same time sum Recalculate ;
  – if dep == maxDepth, Indicates that the current node is at the maximum depth , Add the current node value to sum in ;
  – if dep < maxDepth, Indicates that the current node depth is less than the maximum depth , Skip the node directly ;
• Finally returned sum It must be the sum of the number of nodes at the maximum depth .

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
private:
    int maxDepth;
    int sum;
public:
    void DFS(TreeNode *root, int dep){
    
        if(!root){
    
            return;
        }
        dep++;

        if(dep == maxDepth){
    
            sum += root->val;
        }
        if(dep > maxDepth){
    
            sum = root->val;
            maxDepth = dep;
        }

        DFS(root->left, dep);
        DFS(root->right, dep);
    }

    int deepestLeavesSum(TreeNode* root) {
    
        sum = 0;
        maxDepth = 0;
        DFS(root, 0);
        
        return sum;
    }
};