JAVA 22ms DFS Solution


  • 0
    Z
    private int min = Integer.MAX_VALUE, res = 0;
    public int findClosestLeaf(TreeNode root, int k) {
        dfs(root, k);
        return res;
    }
    private int[] dfs(TreeNode n, int k) {
    	// if find the leaf
        if (n.left == null && n.right == null)  {
            if (n.val == k) {
                min = 0;
                res = k;
            }
            return new int[]{0, n.val == k ? 0 : Integer.MAX_VALUE, n.val};
        }
        int minPathToLeaf = Integer.MAX_VALUE, minPathToK = n.val == k ? 0 : Integer.MAX_VALUE;
        int nv = n.val; // node value
        // for every node, check left and right node to find the
        // minPathToLeaf, minPathToK and leaf value in the min path
        if (n.left != null) {
            int[] t = dfs(n.left, k);
            minPathToLeaf = t[0] + 1;
            if (minPathToK != 0 && t[1] != Integer.MAX_VALUE) 
                minPathToK = t[1] + 1;
            nv = t[2];
        }
        if (n.right != null) {
            int[] t = dfs(n.right, k);
            if (minPathToLeaf > t[0] + 1) {
                minPathToLeaf = t[0] + 1;
                nv = t[2];
            }
            if (minPathToK != 0 && t[1] != Integer.MAX_VALUE) 
                minPathToK = t[1] + 1;
        }
        // if find a path from leaf to k, record the min value
        if (minPathToK != Integer.MAX_VALUE && minPathToLeaf != Integer.MAX_VALUE) {
            if (min > minPathToK + minPathToLeaf) {
                min = minPathToK + minPathToLeaf;
                res = nv;
            }
        }
        return new int[]{minPathToLeaf, minPathToK, nv};
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.