검지offer--두 갈래 나무에 차례대로 흐르는 다음 결점

검지offer--두 갈래 나무에 차례대로 흐르는 다음 결점

1 제목 설명

두 갈래 나무와 그 중의 한 결점을 정하십시오. 순서를 반복하는 다음 결점을 찾아 돌아오십시오.나무의 결점은 좌우 자결점뿐만 아니라 부모 결점을 가리키는 바늘도 포함하고 있음을 주의하십시오.

2 나의 해답: 분류가 불합리해서 오류가 발생했습니다!

토론 불완전, 오류!!분류가 불합리하다!!!
분류 토론:

정해진 결점에 오른쪽 나무가 있으면 중순으로 흐르는 다음은 반드시 오른쪽 나무의 가장 왼쪽 결점으로 정해진다.while 순환을 이용하여 오른쪽 나무의 가장 왼쪽에 있는 결점을 찾아 돌아오면 된다

주어진 결점은 왼쪽 나무뿐이다......이 분류는 불합리하여 오류를 초래하기 쉽다

오류 소스는 다음과 같습니다.

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode!=null && pNode.left==null && pNode.right==null ){
            if(pNode.next!=null){
                pNode=pNode.next;
            }
            return pNode;
        }
        if(pNode.right!=null){
            // ， ， 
            pNode=pNode.right;
            while(pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }
        if(pNode.left!=null){
            if(pNode.next!=null){
                return pNode.next;
            }
        }
        return pNode;
    }
}

코드를 통과하지 않고 답안을 저장했습니다. 제출한 프로그램이 모든 테스트 용례case를 통과하지 못했습니다. 통과율은 25.00%입니다.
테스트 용례: {8,6,10,5,7,9,11},7
출력은 다음과 같아야 합니다.
팔
출력:
육

3 합리적으로 분류하여 정답을 얻다

분류 토론:

정해진 결점에 오른쪽 나무가 있으면 중순으로 흐르는 다음은 반드시 오른쪽 나무의 가장 왼쪽 결점으로 정해진다.while 순환을 이용하여 오른쪽 나무의 가장 왼쪽에 있는 결점을 찾아 돌아오면 된다

주어진 결점에 오른쪽 나무가 없으면 주어진 결점의 부모 노드를 찾습니다.두 가지 상황으로 나누어 토론을 진행한다. 첫째, 결점을 아버지 노드로 정한 왼쪽 트리에 아버지 노드로 직접 되돌아간다.둘째, 결점이 부모 노드인 오른쪽 하위 트리를 지정하면 결점이 부모 노드인 왼쪽 하위 트리를 찾아 부모 노드로 돌아갈 때까지 위로 계속 찾습니다.루트 노드가 조건을 충족시키는 노드가 존재하지 않는 것을 찾으면null로 되돌아옵니다

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null){
            return pNode;
        }
        if(pNode.right!=null){// ， 
            pNode=pNode.right;
            while(pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }
        while(pNode.next!=null){// ， 
            if(pNode==pNode.next.left){
                return pNode.next;
            }
            pNode=pNode.next;
        }
        return null;// ， null
    }
}