2019年5月 – gongel

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

示例:

给定如下二叉树，以及目标和 sum = 22，

/ \

4 8

/ / \

11 13 4

/ \ \

7 2 1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

package gongel;

public class onehundred_twelve {
    /**
     * DFS
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return sum - root.val == 0;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

package gongel;

public class onehundred_twelve {

/**

* DFS

public boolean hasPathSum(TreeNode root, int sum) {

if (root == null)

return false;

if (root.left == null && root.right == null)

return sum - root.val == 0;

return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == nullptr)
            return false;
        if (root->left == nullptr && root->right == nullptr)
            return sum - root->val == 0;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

bool hasPathSum(TreeNode *root, int sum) {

if (root == nullptr)

return false;

if (root->left == nullptr && root->right == nullptr)

return sum - root->val == 0;

return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);

}

};

113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

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

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

示例:

给定如下二叉树，以及目标和 sum = 22，

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

[

[5,4,11,2],

[5,8,4,5]

]

package gongel;

import java.util.ArrayList;
import java.util.List;

public class Onehundred_thirteen {
    /**
     * DFS+回溯
     */
    private List<List<Integer>> ans = new ArrayList<>();

    public void finpath(TreeNode root, int sum, List<Integer> temp) {
        if (root != null) {
            if (root.left == null && root.right == null && sum == root.val) {//必须在根节点结束
                temp.add(root.val);
                ans.add(new ArrayList<>(temp));//一定要新建一个List，否则ans中只存在一个temp
                temp.remove(temp.size() - 1);
                return;
            }
            temp.add(root.val);
            finpath(root.left, sum - root.val, temp);
            finpath(root.right, sum - root.val, temp);
            temp.remove(temp.size() - 1);//回溯
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<Integer> temp = new ArrayList<>();
        finpath(root, sum, temp);
        return ans;
    }
}

package gongel;

import java.util.ArrayList;

import java.util.List;

public class Onehundred_thirteen {

/**

* DFS+回溯

private List<List<Integer>> ans = new ArrayList<>();

public void finpath(TreeNode root, int sum, List<Integer> temp) {

if (root != null) {

if (root.left == null && root.right == null && sum == root.val) {//必须在根节点结束

temp.add(root.val);

ans.add(new ArrayList<>(temp));//一定要新建一个List，否则ans中只存在一个temp

temp.remove(temp.size() - 1);

return;

}

temp.add(root.val);

finpath(root.left, sum - root.val, temp);

finpath(root.right, sum - root.val, temp);

temp.remove(temp.size() - 1);//回溯

}

public List<List<Integer>> pathSum(TreeNode root, int sum) {

List<Integer> temp = new ArrayList<>();

finpath(root, sum, temp);

return ans;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode *root, int sum) {
        vector<int> temp;
        vector<vector<int>> ans;
        helper(root, sum, temp, ans);
    }

    void helper(TreeNode *root, int sum, vector<int> &temp, vector<vector<int>> &ans) {
        if (root == nullptr)
            return;
        if (root->left == nullptr && root->right == nullptr) {
            if (sum == root->val) {
                temp.push_back(root->val);
                ans.push_back(temp);
                temp.pop_back();
            }
        }
        temp.push_back(root->val);
        helper(root->left, sum - root->val, temp, ans);
        helper(root->right, sum - root->val, temp, ans);
        temp.pop_back();
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

vector<vector<int>> pathSum(TreeNode *root, int sum) {

vector<int> temp;

vector<vector<int>> ans;

helper(root, sum, temp, ans);

}

void helper(TreeNode *root, int sum, vector<int> &temp, vector<vector<int>> &ans) {

if (root == nullptr)

return;

if (root->left == nullptr && root->right == nullptr) {

if (sum == root->val) {

temp.push_back(root->val);

ans.push_back(temp);

temp.pop_back();

}

temp.push_back(root->val);

helper(root->left, sum - root->val, temp, ans);

helper(root->right, sum - root->val, temp, ans);

temp.pop_back();

}

};

124. 二叉树中的最大路径和略难

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

/ \

2 3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

-10

/ \

9 20

/ \

15 7

输出: 42

package gongel;

public class Onehundred_twentyFour {
    /**
     * 略难！
     * 最大路径和：根据当前节点的角色，路径和可分为两步：
     * 一：当前节点作为父节点的一个子节点
     * 1.只有当前节点
     * 2.当前节点+左子树
     * 3.当前节点+右子树
     * 这三种情况的最大值，第四种情况不可能，因为当前节点+左右子树和父节点就不在一条路径上
     *
     * 二：以当前节点为根节点
     * 1.只有当前节点
     * 2.当前节点+左子树
     * 3.当前节点+右子树
     * 4.当前节点+左右子树
     * 这四种情况的最大值即为以当前节点为根的最大路径和
     * 此最大值要和已经保存的最大值比较，得到整个树的最大路径值
     */
    private int maxValue = Integer.MIN_VALUE;

    public int getMaxValue(TreeNode root) {
        if (root == null)
            return 0;
        int leftMax = getMaxValue(root.left);
        int rightMax = getMaxValue(root.right);
        int max1 = leftMax + root.val;
        int max2 = rightMax + root.val;
        int max3 = leftMax + rightMax + root.val;
        //下面没有与root.val比较是因为maxValue已经初始化root.val，但也可以加上比较
        maxValue = Math.max(maxValue, Math.max(max1, Math.max(max2, Math.max(max3, root.val))));
        //返回的值不包括“当前节点+左右子树”，否则与父节点断开
        return Math.max(root.val, Math.max(max1, max2));
    }


    public int maxPathSum(TreeNode root) {
        if (root == null)
            return 0;
        //maxValue = root.val;maxValue已经为最小值了，
        getMaxValue(root);
        return maxValue;
    }
}

package gongel;

public class Onehundred_twentyFour {

/**

* 略难！

* 最大路径和：根据当前节点的角色，路径和可分为两步：

* 一：当前节点作为父节点的一个子节点

* 1.只有当前节点

* 2.当前节点+左子树

* 3.当前节点+右子树

* 这三种情况的最大值，第四种情况不可能，因为当前节点+左右子树和父节点就不在一条路径上

* 二：以当前节点为根节点

* 1.只有当前节点

* 2.当前节点+左子树

* 3.当前节点+右子树

* 4.当前节点+左右子树

* 这四种情况的最大值即为以当前节点为根的最大路径和

* 此最大值要和已经保存的最大值比较，得到整个树的最大路径值

private int maxValue = Integer.MIN_VALUE;

public int getMaxValue(TreeNode root) {

if (root == null)

return 0;

int leftMax = getMaxValue(root.left);

int rightMax = getMaxValue(root.right);

int max1 = leftMax + root.val;

int max2 = rightMax + root.val;

int max3 = leftMax + rightMax + root.val;

//下面没有与root.val比较是因为maxValue已经初始化root.val，但也可以加上比较

maxValue = Math.max(maxValue, Math.max(max1, Math.max(max2, Math.max(max3, root.val))));

//返回的值不包括“当前节点+左右子树”，否则与父节点断开

return Math.max(root.val, Math.max(max1, max2));

}

public int maxPathSum(TreeNode root) {

if (root == null)

return 0;

//maxValue = root.val;maxValue已经为最小值了，

getMaxValue(root);

return maxValue;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int max_val = INT_MIN;
        get_max(root, max_val);
        return max_val;
    }

    int get_max(TreeNode *root, int &max_val) {
        if (root == nullptr)
            return 0;
        int left_max = get_max(root->left, max_val);
        int right_max = get_max(root->right, max_val);
        int max_one = root->val + left_max;
        int max_two = root->val + right_max;
        int max_three = root->val + left_max + right_max;
        max_val = max(max_val, max(max_one, max(max_two, max(max_three, root->val))));
        return max(root->val, max(max_one, max_two));
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

int maxPathSum(TreeNode *root) {

int max_val = INT_MIN;

get_max(root, max_val);

return max_val;

}

int get_max(TreeNode *root, int &max_val) {

if (root == nullptr)

return 0;

int left_max = get_max(root->left, max_val);

int right_max = get_max(root->right, max_val);

int max_one = root->val + left_max;

int max_two = root->val + right_max;

int max_three = root->val + left_max + right_max;

max_val = max(max_val, max(max_one, max(max_two, max(max_three, root->val))));

return max(root->val, max(max_one, max_two));

}

};

129. 求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

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

示例 1:

输入: [1,2,3]

/ \

2 3

输出: 25

解释:

从根到叶子节点路径 1->2 代表数字 12.

从根到叶子节点路径 1->3 代表数字 13.

因此，数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]

/ \

9 0

/ \

5 1

输出: 1026

解释:

从根到叶子节点路径 4->9->5 代表数字 495.

从根到叶子节点路径 4->9->1 代表数字 491.

从根到叶子节点路径 4->0 代表数字 40.

因此，数字总和 = 495 + 491 + 40 = 1026.

法一：不需要回溯所以可以直接算

public class Onehundred_twentyNine {
    /**
     * dfs
     */
    private int ans = 0;

    public void helper(TreeNode root, int father) {
        if (root != null) {
            int current = 10 * father + root.val;
            if (root.left == null && root.right == null) {//到达叶子节点
                ans += current;
                return;
            }
            helper(root.left, current);
            helper(root.right, current);
        }
    }

    public int sumNumbers(TreeNode root) {
        helper(root, 0);
        return ans;
    }
}


法二：利用回溯的方法，但没有回溯
public class Onehundred_twentyNine {
    private int ans = 0;

    public void dfs(TreeNode root, String path) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            String newPth = path + String.valueOf(root.val);
            ans += Integer.parseInt(newPth);
            return;
        }
        String newPth = path + String.valueOf(root.val);
        dfs(root.left, newPth);
        dfs(root.right, newPth);
    }

    public int sumNumbers(TreeNode root) {
        if (root == null)
            return 0;
        dfs(root, "");
        return ans;
    }
}

法一：不需要回溯所以可以直接算

public class Onehundred_twentyNine {

/**

* dfs

private int ans = 0;

public void helper(TreeNode root, int father) {

if (root != null) {

int current = 10 * father + root.val;

if (root.left == null && root.right == null) {//到达叶子节点

ans += current;

return;

}

helper(root.left, current);

helper(root.right, current);

}

public int sumNumbers(TreeNode root) {

helper(root, 0);

return ans;

}

法二：利用回溯的方法，但没有回溯

public class Onehundred_twentyNine {

private int ans = 0;

public void dfs(TreeNode root, String path) {

if (root == null)

return;

if (root.left == null && root.right == null) {

String newPth = path + String.valueOf(root.val);

ans += Integer.parseInt(newPth);

return;

}

String newPth = path + String.valueOf(root.val);

dfs(root.left, newPth);

dfs(root.right, newPth);

}

public int sumNumbers(TreeNode root) {

if (root == null)

return 0;

dfs(root, "");

return ans;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int ans = 0;
        helper(root, "", ans);
        return ans;
    }

    void helper(TreeNode *root, string path, int &ans) {
        if (root == nullptr)
            return;
        if (root->left == nullptr && root->right == nullptr) {
            stringstream ss;
            ss << (path + to_string(root->val));
            int temp;
            ss >> temp;
            ans += temp;
        }
        helper(root->left, path + to_string(root->val), ans);
        helper(root->right, path + to_string(root->val), ans);
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

int sumNumbers(TreeNode *root) {

int ans = 0;

helper(root, "", ans);

return ans;

}

void helper(TreeNode *root, string path, int &ans) {

if (root == nullptr)

return;

if (root->left == nullptr && root->right == nullptr) {

stringstream ss;

ss << (path + to_string(root->val));

int temp;

ss >> temp;

ans += temp;

}

helper(root->left, path + to_string(root->val), ans);

helper(root->right, path + to_string(root->val), ans);

}

};

257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

给定一个二叉树，返回所有从根节点到叶子节点的路径。

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

示例:

输入:

/ \

2 3

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

package gongel;

import java.util.ArrayList;
import java.util.List;

public class Twohundred_firtySeven {
    /**
     * dfs:不用回溯，因为link并没有改变，一般用list必须对回溯，回溯可以返回上一级
     */
    private List<String> ans = new ArrayList<>();

    public void dfs(TreeNode root, String link) {
        if (root != null) {
            if (root.left == null && root.right == null) {//到达叶子节点
                ans.add(link + root.val);//叶子节点不用+"->"，比首节点更好判断
                return;
            }
            dfs(root.left, link + root.val + "->");//不需要回溯，因为link没有改变
            dfs(root.right, link + root.val + "->");
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        if (root != null)
            dfs(root, new String());
        return ans;
    }
}

package gongel;

import java.util.ArrayList;

import java.util.List;

public class Twohundred_firtySeven {

/**

* dfs:不用回溯，因为link并没有改变，一般用list必须对回溯，回溯可以返回上一级

private List<String> ans = new ArrayList<>();

public void dfs(TreeNode root, String link) {

if (root != null) {

if (root.left == null && root.right == null) {//到达叶子节点

ans.add(link + root.val);//叶子节点不用+"->"，比首节点更好判断

return;

}

dfs(root.left, link + root.val + "->");//不需要回溯，因为link没有改变

dfs(root.right, link + root.val + "->");

}

public List<String> binaryTreePaths(TreeNode root) {

if (root != null)

dfs(root, new String());

return ans;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode *root) {
        vector<string> ans;
        helper(root, "", ans);
        return ans;
    }

    void helper(TreeNode *root, string path, vector<string> &ans) {
        if (root == nullptr)
            return;
        if (root->left == nullptr && root->right == nullptr) {
            ans.push_back(path + to_string(root->val));
            return;
        }
        helper(root->left, path + to_string(root->val) + "->", ans);
        helper(root->right, path + to_string(root->val) + "->", ans);
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

vector<string> binaryTreePaths(TreeNode *root) {

vector<string> ans;

helper(root, "", ans);

return ans;

}

void helper(TreeNode *root, string path, vector<string> &ans) {

if (root == nullptr)

return;

if (root->left == nullptr && root->right == nullptr) {

ans.push_back(path + to_string(root->val));

return;

}

helper(root->left, path + to_string(root->val) + "->", ans);

helper(root->right, path + to_string(root->val) + "->", ans);

}

};

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

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

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

返回 3。和等于 8 的路径有:

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

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

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

/ \

5 -3

/ \ \

3 2 11

/ \ \

3 -2 1

返回 3。和等于 8 的路径有:

1. 5 -> 3

2. 5 -> 2 -> 1

3. -3 -> 11

package gongel;

public class Fourhundred_thirtySeven {
    /**
     * 不从根节点出发即树的遍历，不从叶节点结束即不需要判断是否到了叶节点
     * 先序遍历（任何遍历都可以）每一个节点，然后每个节点进行dfs
     */
    private int ans = 0;

    public void dfs(TreeNode root, int sum) {
        if (root != null) {
            if (sum == root.val) {
                ans++;
//                return;  不需要return，因为即使出现负值，还会有子节点加上去
            }
            dfs(root.left, sum - root.val);
            dfs(root.right, sum - root.val);
        }
    }

    public int pathSum(TreeNode root, int sum) {
        if (root != null) {
            dfs(root, sum);
            pathSum(root.left, sum);
            pathSum(root.right, sum);
        }
        return ans;
    }
}

package gongel;

public class Fourhundred_thirtySeven {

/**

* 不从根节点出发即树的遍历，不从叶节点结束即不需要判断是否到了叶节点

* 先序遍历（任何遍历都可以）每一个节点，然后每个节点进行dfs

private int ans = 0;

public void dfs(TreeNode root, int sum) {

if (root != null) {

if (sum == root.val) {

ans++;

// return; 不需要return，因为即使出现负值，还会有子节点加上去

}

dfs(root.left, sum - root.val);

dfs(root.right, sum - root.val);

}

public int pathSum(TreeNode root, int sum) {

if (root != null) {

dfs(root, sum);

pathSum(root.left, sum);

pathSum(root.right, sum);

}

return ans;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    int ans = 0;
public:
    int pathSum(TreeNode *root, int sum) {
        if (root != nullptr) {
            helper(root, sum);
            pathSum(root->left, sum);
            pathSum(root->right, sum);
        }
        return ans;
    }

    void helper(TreeNode *root, int sum) {
        if (root == nullptr)
            return;
        if (sum == root->val)
            ans += 1;
        helper(root->left, sum - root->val);
        helper(root->right, sum - root->val);
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

private:

int ans = 0;

public:

int pathSum(TreeNode *root, int sum) {

if (root != nullptr) {

helper(root, sum);

pathSum(root->left, sum);

pathSum(root->right, sum);

}

return ans;

}

void helper(TreeNode *root, int sum) {

if (root == nullptr)

return;

if (sum == root->val)

ans += 1;

helper(root->left, sum - root->val);

helper(root->right, sum - root->val);

}

};

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树

/ \

2 3

/ \

4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

package gongel;

public class Fivehundred_fortyThree {
    /**
     * 和 124题二叉树中的最大路径和 有异曲同工之妙
     */
    public int ans = 0;

    public int dfs(TreeNode root) {
        if (root == null)
            return 0;
        int left = dfs(root.left);//返回左子树的最大深度
        int right = dfs(root.right);//返回右子树的最大深度
        ans = Math.max(ans, left + right);//最终结果的最大值
        return Math.max(left, right) + 1;//求当前节点的深度（左右子树的高度最大值）
    }

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
}

package gongel;

public class Fivehundred_fortyThree {

/**

* 和 124题二叉树中的最大路径和有异曲同工之妙

public int ans = 0;

public int dfs(TreeNode root) {

if (root == null)

return 0;

int left = dfs(root.left);//返回左子树的最大深度

int right = dfs(root.right);//返回右子树的最大深度

ans = Math.max(ans, left + right);//最终结果的最大值

return Math.max(left, right) + 1;//求当前节点的深度（左右子树的高度最大值）

}

public int diameterOfBinaryTree(TreeNode root) {

dfs(root);

return ans;

}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int diameterOfBinaryTree(TreeNode *root) {
        int max_val = 0;
        helper(root, max_val);
        return max_val;
    }

    int helper(TreeNode *root, int &max_val) {
        if (root == nullptr)
            return 0;
        int left_max = helper(root->left, max_val);
        int right_max = helper(root->right, max_val);
        max_val = max(max_val, left_max + right_max);//高度=路径加+1
        return max(left_max, right_max) + 1;//高度
    }
};

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

int diameterOfBinaryTree(TreeNode *root) {

int max_val = 0;

helper(root, max_val);

return max_val;

}

int helper(TreeNode *root, int &max_val) {

if (root == nullptr)

return 0;

int left_max = helper(root->left, max_val);

int right_max = helper(root->right, max_val);

max_val = max(max_val, left_max + right_max);//高度=路径加+1

return max(left_max, right_max) + 1;//高度

}

};

988. 从叶结点开始的最小字符串

给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。

找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）

 

示例 1：



输入：[0,1,2,3,4,3,4]
输出："dba"
示例 2：



输入：[25,1,3,1,3,0,2]
输出："adz"
示例 3：



输入：[2,2,1,null,1,0,null,0]
输出："abc"
 

提示：

给定树的结点数介于 1 和 8500 之间。
树中的每个结点都有一个介于 0 和 25 之间的值。

给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。

找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）

示例 1：

输入：[0,1,2,3,4,3,4]

输出："dba"

示例 2：

输入：[25,1,3,1,3,0,2]

输出："adz"

示例 3：

输入：[2,2,1,null,1,0,null,0]

输出："abc"

提示：

给定树的结点数介于 1 和 8500 之间。

树中的每个结点都有一个介于 0 和 25 之间的值。

法一：回溯

public class Ninehundred_eightyEight {
    /**
     * dfs+回溯
     * 从根节点到叶子节点：逆序插入
     * 每次到达叶子结点就与全局ans进行比较更新
     */
    private String ans = null;

    public void dfs(TreeNode root, StringBuffer sb) {
        if (root != null) {
            if (root.left == null && root.right == null) {
                sb.insert(0, (char) (root.val + 'a'));
                if (ans == null || sb.toString().compareTo(ans) < 0) {
                    ans = sb.toString();
                }
                sb.deleteCharAt(0);
                return;
            }
            sb.insert(0, (char) (root.val + 'a'));
            dfs(root.left, sb);
            dfs(root.right, sb);
            sb.deleteCharAt(0);
        }
    }

    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuffer());
        return ans;
    }
}

法二：不回溯，因为path没有改变
public class Ninehundred_eightyEight {
    private String ans = null;

    public void dfs(TreeNode root, StringBuffer path) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            StringBuffer newPath = new StringBuffer(path);
            newPath.insert(0, (char) 'a' + root.val);
            if (ans == null)
                ans = newPath.toString();
            if (ans.compareTo(newPath.toString()) > 0)
                ans = newPath.toString();
            return;
        }
        StringBuffer newPath = new StringBuffer(path);
        newPath.insert(0, (char) 'a' + root.val);
        dfs(root.left, newPath);
        dfs(root.right, newPath);
    }

    public String smallestFromLeaf(TreeNode root) {
        if (root == null)
            return new String();
        dfs(root, new StringBuffer());
        return ans;
    }
}

法一：回溯

public class Ninehundred_eightyEight {

/**

* dfs+回溯

* 从根节点到叶子节点：逆序插入

* 每次到达叶子结点就与全局ans进行比较更新

private String ans = null;

public void dfs(TreeNode root, StringBuffer sb) {

if (root != null) {

if (root.left == null && root.right == null) {

sb.insert(0, (char) (root.val + 'a'));

if (ans == null || sb.toString().compareTo(ans) < 0) {

ans = sb.toString();

}

sb.deleteCharAt(0);

return;

}

sb.insert(0, (char) (root.val + 'a'));

dfs(root.left, sb);

dfs(root.right, sb);

sb.deleteCharAt(0);

}

public String smallestFromLeaf(TreeNode root) {

dfs(root, new StringBuffer());

return ans;

}

法二：不回溯，因为path没有改变

public class Ninehundred_eightyEight {

private String ans = null;

public void dfs(TreeNode root, StringBuffer path) {

if (root == null)

return;

if (root.left == null && root.right == null) {

StringBuffer newPath = new StringBuffer(path);

newPath.insert(0, (char) 'a' + root.val);

if (ans == null)

ans = newPath.toString();

if (ans.compareTo(newPath.toString()) > 0)

ans = newPath.toString();

return;

}

StringBuffer newPath = new StringBuffer(path);

newPath.insert(0, (char) 'a' + root.val);

dfs(root.left, newPath);

dfs(root.right, newPath);

}

public String smallestFromLeaf(TreeNode root) {

if (root == null)

return new String();

dfs(root, new StringBuffer());

return ans;

}

class Solution {
public:
    string smallestFromLeaf(TreeNode *root) {
        string ans;
        helper(root, "", ans);
        return ans;
    }

    void helper(TreeNode *root, string path, string &ans) {
        if (root == nullptr)
            return;
        if (root->left == nullptr && root->right == nullptr) {
            path.insert(0, 1, (char) (root->val + 'a'));
            if (ans.empty() || ans > path)
                ans = path;
            return;
        }
        path.insert(0, 1, (char) (root->val + 'a'));
        helper(root->left, path, ans);
        helper(root->right, path, ans);
    }
};

class Solution {

public:

string smallestFromLeaf(TreeNode *root) {

string ans;

helper(root, "", ans);

return ans;

}

void helper(TreeNode *root, string path, string &ans) {

if (root == nullptr)

return;

if (root->left == nullptr && root->right == nullptr) {

path.insert(0, 1, (char) (root->val + 'a'));

if (ans.empty() || ans > path)

ans = path;

return;

}

path.insert(0, 1, (char) (root->val + 'a'));

helper(root->left, path, ans);

helper(root->right, path, ans);

}

};

return the last

月份：2019年5月

RNN

Attention

一. 定义

二. 分类

三. 相似度计算

四. 常见task

五.常见问题

六. 参考

二叉树路径问题

LightGBM

一.概述

二. 详述

三. 参考

Dialogue system papers

ICSL

Other

2019年五月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31