LintCode - 두 갈래 트리의 최대 노드(일반)

1517 단어
판권 성명: 본고는 블로거의 오리지널 문장으로 블로거의 허락 없이 전재할 수 없습니다.
난이도: 일반
요구 사항:
두 갈래 트리를 지정하고 모든 경로에서 각 노드가 합쳐져 목표 값을 지정하는 경로를 찾아냅니다.유효한 경로는 루트 노드에서 잎 노드까지의 경로를 가리킨다.
예:
다음 두 갈래 나무를 보여 줍니다.
     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5 

값이 3인 노드를 되돌려줍니다.
생각:
반복 비교
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @return the max ndoe
     */
    public TreeNode maxNode(TreeNode root) {
        // Write your code here
        return getMaxNode(root);
    }
    
    
    private TreeNode getMaxNode(TreeNode node){
        if(node == null){
            return node;
        }    
    
        TreeNode maxLeft = getMaxNode(node.left);
        TreeNode maxRight = getMaxNode(node.right);
        
        if(maxLeft != null && maxRight != null){
            TreeNode max = maxLeft.val > maxRight.val ? maxLeft : maxRight;
            return node.val > max.val ? node : max;
        } else {
            if(maxLeft != null){
                return node.val > maxLeft.val ? node : maxLeft;
            }
            if(maxRight != null){
                return node.val > maxRight.val ? node : maxRight;
            }
        }
        return node;
    }
}

좋은 웹페이지 즐겨찾기