Java DFS Solution


  • 0
    Z

    The idea is simple, traversing in depth-first order, do two operations at once.

    1. If the maximum path passes through parent of the current node, there are three possible ways how the path can continue. a) Stop at the current node, b) Go left from the current node, c) Go right from the current node. Because we are searching for the maximum path, return maximum of (a,b,c) to the upper level.
    2. It is possible that the maximum path does not pass through parent of the current node. Therefore check if the maximum path in current sub-tree is greater than currently known maximum path. This way always maximize the answer.
    public class Solution {
        int ans;
        public int maxPathSum(TreeNode root) {
            ans = Integer.MIN_VALUE;
            if(root == null) return 0;
            traverse(root);
            return ans;
        }
        
        public int traverse(TreeNode node){
        	if(node.right == null && node.left == null){ 
        	    ans = Math.max(ans, node.val);
        	    return node.val;
        	}
        	int leftMax = 0, rightMax = 0;	
        	if(node.left != null){
        		leftMax = traverse(node.left);
        	}
        	if(node.right != null){
        		rightMax  = traverse(node.right);	
        	}
        	int max = Math.max(node.val, Math.max(leftMax, rightMax) + node.val); //max to be returned
        	ans = Math.max(Math.max(ans, leftMax+rightMax+node.val), max); // max in the current sub-tree
        	return max;
        }
    }

Log in to reply
 

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