[数据结构与算法]leetcode-Tree

leetcode257

class Solution {
    List<String> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        getPath(root);
        return res;
    }

    private void getPath(TreeNode root) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            res.add(listToString(path));
        }
        if (root.left!=null)getPath(root.left);
        if (root.right!=null)getPath(root.right);
        path.remove(path.size()-1);
    }

    private String listToString(List<Integer> path) {
        StringBuilder builder = new StringBuilder();
        for (Integer integer : path) {
            builder.append(integer).append("->");
        }
        builder.delete(builder.length() - 2, builder.length());
        return builder.toString();
    }
}

687. 最长同值路径

*题解：*递归函数的作用：当前节点的最长同值路径（左子树+右子树+当前节点）
因为当前节点的最长同值路径是由左右子树节点的和，所以采用后序遍历。

class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root==null)return 0;
        longPath(root,root.val);
        return res;
    }

    private int longPath(TreeNode root,int pre) {
        if (root == null) return 0;
         //计算左右孩子最长路径
        int left = longPath(root.left,root.val);
        int right = longPath(root.right,root.val);
        int sum = left+right;
        //当前节点最长路径更新ans
        res = Math.max(res, sum);
        //等于父亲节点值时，返回  max（左最长路径，右最长路径）+ 1
        if (root.val==pre)return Math.max(left, right)+1;
        //不等于父亲节点时，返回0
        return 0;
    }
}