트리 깊이 우선 순위 검색

트리에 대한 검색 문제는 일반적으로 귀속을 통해 쓸 수 있다.하나.제목: Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. 
For example:
Given the below binary tree and sum = 22, 
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

문제 풀이 사상 제목은 두 갈래 나무를 주고 각 노드는 하나의 값에 대응하며 지정된 나무를 준다는 뜻이다.그리고 뿌리 노드에서 시작해서 잎 노드로 가는 경로가 있는지 물어보세요. 그 경로는 바로 그 값과 같습니다.방법은 간단한 DFS입니다. 만약에 잎 노드가 그 값과 딱 맞으면 True로 돌아가고, 부족하거나 초과하면 False로 돌아갑니다.코드:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution {
public:

    void dfs(TreeNode* root, int sum, bool& ret){
        if(sum == root -> val && !root -> left && !root -> right){
            ret = true;
            return;
        }
        if(!root-> left && !root -> right)
          return;
        if(root -> left)
          dfs(root -> left, sum - root -> val, ret);
        if(root -> right)
          dfs(root -> right, sum - root -> val, ret);
    }
    
    bool hasPathSum(TreeNode* root, int sum) {
        bool ret = false;
        if(root == NULL)
          return ret;
        dfs(root, sum, ret);
        return ret;
    }
 ：
public class Solution {
 bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) return false;
        if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
}

변형 1.Leetcode 113. Path Sum II 경로 및 2

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. 
For example:
Given the below binary tree and sum = 22, 
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

문제 풀이 사상은 이전 문제와 유사하지만 이전 문제는 이런 경로가 존재하는지 판독하는 것이고 이 문제는 이런 경로를 찾아내는 것이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


 /**
  *  ， ， track ， dfs ， dfs ， 0 ， 。
  * */
public class Solution {
    List> list;
    LinkedList track;
    public void dfs(TreeNode root,int sum){
        if(root==null)
            return;
        sum-=root.val;
        track.add(root.val);
        if(sum==0 && root.left==null && root.right==null)
            list.add((LinkedList)track.clone());
        dfs(root.left,sum);
        dfs(root.right,sum);
        track.remove(track.size()-1);

    }
    public List> pathSum(TreeNode root, int sum) {
        this.list=new ArrayList>();
        this.track=new LinkedList();
        dfs(root,sum);
        return this.list;
    }
}

변형Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

예.

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

코드:

/**
 * 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 {
public:
    int pathSum(TreeNode* root, int sum) {
        if(root == NULL)
          return 0;
        return dfs(root, sum) + pathSum(root -> left, sum) + pathSum(root -> right, sum);
    }
    
    int dfs(TreeNode* root, int sum){
        int ret = 0;
        if(root == NULL)
          return ret;
        if(sum == root -> val)
          ret ++;
        ret += dfs(root -> left, sum - root -> val);
        ret += dfs(root -> right, sum - root -> val);
        return ret;
    }
};

아래 두 줄도 비슷한 두 줄로 뿌리에서 잎사귀 노드까지의 모든 경로를 찾아야 한다.전자는 뿌리에서 잎 노드까지의 모든 경로를 출력하고 그 다음은 모든 경로 중의 최소 깊이를 구한다. 두 번째 문제를 풀 때 나는 먼저 첫 번째 문제의 사고방식에 따라 뿌리에서 잎 노드까지의 모든 경로를 구한 다음에 그 중에서 최소 깊이를 찾아낸다.문제 1.Binary Tree Paths Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree:

 1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

코드:

/**
 * 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 {
public:
    void binaryTreePath(vector& result, TreeNode* root, string t) {
    if(!root->left && !root->right) {
        result.push_back(t);
        return;
    }

    if(root->left) binaryTreePath(result, root->left, t + "->" + to_string(root->left->val));
    if(root->right) binaryTreePath(result, root->right, t + "->" + to_string(root->right->val));
}

vector binaryTreePaths(TreeNode* root) {
    vector result;
    if(!root) return result;
    
    binaryTreePath(result, root, to_string(root->val));
    return result;
}    
};

문제2.Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 문제 풀이 사고방식: 먼저 상기 문제의 사고방식에 따라 모든 뿌리에서 잎 노드까지의 깊이를 얻어서 하나의vector에 넣은 다음에 전체vector를 훑어보고 가장 작은 경로의 깊이를 찾아낸다. 원래는 전체 과정이 시간이 초과될 줄 알았는데 AC를 생각하지 못했다.코드:

/**
 * 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 {
public:
    void dfs(vector& allDepth, TreeNode* root, int depth){
        if(root -> left == NULL && root -> right == NULL){
            allDepth.push_back(depth);
            return;
        }
        if(root->left) dfs(allDepth, root->left, depth + 1);
        if(root->right) dfs(allDepth, root->right, depth + 1);
          
    }
    
    int minDepth(TreeNode* root) {
        if(root == NULL)
          return 0;
        vector allDepth;
        int depth = 1;
        dfs(allDepth, root, depth);
        int min = allDepth[0];
        for(int i = 1; i < allDepth.size(); i ++){
            if(allDepth[i] < min)
              min = allDepth[i];
        }
        return min;
    }
};