[数据结构与算法]找出二叉树的最长路径

题目

? ? ? ? （PS: 遇到的笔试题，下面回忆大概题意）

? ? ? ? 找出二叉树的最长路径，最长路径可能有多条，输出任意一条即可。

? ? ? ? 例如如下二叉树最长路径有两条：5，3，4 和 5，3，6。输出任意一条即可。????????????????

????????节点定义：

class TreeNode {
    int val = 0;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

做法1

? ? ? ? 可以先求出二叉树的深度（例如，上述二叉树的深度为3）。然后再遍历一遍二叉树，找到长度为3的路径即可。

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

/**
 * @author passerbyYSQ
 * @create 2021-07-13 19:24
 */
public class MaxPath {

    private static List<Integer> ans;
    private static int h;

    public static void main(String[] args) {
        // 样例
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        node5.left = node1;
        node5.right = node3;
        node3.left = node4;
        node3.right = node6;

        h = maxHeight(node5);

        dfs(node5, new LinkedList<>());

        System.out.println(ans); // [5, 3, 6]
    }

    public static void dfs(TreeNode root, LinkedList<Integer> path) {
        if (root == null) {
            return;
        }

        path.add(root.val);

        if (root.left == null && root.right == null) {
            //System.out.println(path);
            if (path.size() == h) {
                // ans = path; // 错误。浅拷贝
                ans = new ArrayList<>(path);  // 深拷贝
            }
        }
        dfs(root.left, path);
        dfs(root.right, path);

        path.removeLast();
    }

    public static int maxHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int t1 = maxHeight(root.left);
        int t2 = maxHeight(root.right);
        return Math.max(t1, t2) + 1;
    }
}

?做法2

? ? ? ? 在递归求树的深度，回溯的过程中，就可以记录最长的路径。只不过这个路径是反序的，reverse一下就可以了。

mport java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author passerbyYSQ
 * @create 2021-07-13 19:31
 */
public class MaxPath1 {

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

    public static void main(String[] args) {
        // 样例
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        node5.left = node1;
        node5.right = node3;
        node3.left = node4;
        node3.right = node6;

        dfs(node5);

        // 还需要将根节点加进去
        ans.add(node5.val);

        // reverse
        Collections.reverse(ans);

        System.out.println(ans); // [5, 3, 4]
    }

    public static int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int t1 = dfs(root.left);
        int t2 = dfs(root.right);

        // 回溯
        if (t1 >= t2) {
            ans.add(root.left.val);
        } else {
            ans.add(root.right.val);
        }

        return Math.max(t1, t2) + 1;
    }

}