Lowest Common Ancestor of a Binary Tree|Java 최 단 코드 구현

860 단어 tree
원본 링크:
236. Lowest Common Ancestor of a Binary Tree
[사고방식]
화해시키다 Lowest Common Ancestor of a Binary Tree 다른 건이 이 진 트 리 의 값 은 중복 되 고 노드 의 크기 순서 가 규칙 적 이지 않 으 면 깊이 로 옮 겨 다 닐 수 밖 에 없습니다.그러나 분명 한 것 은 p,q 노드 는 공동 조상 들 의 좌우 양쪽 에서 가장 낮 게 별거 하 는 것 이다(p 또는 q 자체 가 조상 을 제외).
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode leftSub = lowestCommonAncestor(root.left, p, q);
        TreeNode rightSub = lowestCommonAncestor(root.right, p, q);
        if (leftSub != null && rightSub != null) return root;
        return leftSub != null ? leftSub : rightSub;
    }

31 / 31 test cases passed. Runtime: 12 ms  Your runtime beats 73.85% of javasubmissions.
최적화 환영 합 니 다!

좋은 웹페이지 즐겨찾기