두 갈래 트리 최대치 경로 구하기

비교적 간단한 두 갈래 나무 제목은 처음에는 잎 노드에서 다른 잎 노드로 가는 경로의 최대치를 찾아야 한다고 생각했지만 제목은 실제로start|end는 임의의 노드가 될 수 있고 실현 과정은 약간 다르지만 사고방식은 대체적으로 같다.
제목:
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1/\2 3 Return 6.
코드 구현:

public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root==null)
            return 0;
        int[] res=new int[1];
        res[0]=Integer.MIN_VALUE;
        maxDfs(root,res);
        return res[0];
    }
    private int maxDfs(TreeNode root,int[] res){
        int curRootSum=root.val;
        int depthMax=0;
        int subMax;
        if(root.left!=null){
            subMax=maxDfs(root.left,res);
            if(subMax>0) {
                depthMax = Math.max(depthMax,subMax);
                curRootSum += subMax;
            }
        }
        if(root.right!=null){
            subMax=maxDfs(root.right,res);
            if(subMax>0) {
                depthMax = Math.max(depthMax,subMax);
                curRootSum += subMax;
            }
        }
        res[0]=Math.max(res[0],curRootSum);
        return depthMax+root.val;
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CODE[VS] 2080 특이한 질수 갈비뼈

제목 설명Description 농민 존의 암소는 항상 가장 좋은 갈비뼈를 만들어 낸다.너는 농민 존과 미국 농업부가 갈비뼈 하나하나에 표시한 숫자를 통해 그것들을 알아볼 수 있다.농민 존은 그가 구매자에게 판매한 것...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

두 갈래 트리 최대치 경로 구하기

좋은 웹페이지 즐겨찾기