검지offer---이차수 중의 다음 노드

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

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 null;
        }
        if(pNode.right != null){
            return getNextNode(pNode.right);
        }
        
        if(pNode.next == null){
            return null;
        }
        if(pNode.next.left == pNode){
            return pNode.next;
        }
        while(pNode.next.right == pNode){
            pNode = pNode.next;
            if(pNode.next == null){
                return null;
            }
        }
        return pNode.next;
    }
    public TreeLinkNode getNextNode(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }
        TreeLinkNode result = null;
        result = getNextNode(pNode.left);
        if(result == null)
            result = pNode;
        return result;
    }
}

중서 역주행은 노드를 먼저 역주행하는 왼쪽 나무, 그 다음은 노드 자체, 그 다음은 노드의 오른쪽 나무..

앞의 순서는 먼저 노드 자체, 그 다음에 왼쪽 나무, 그 다음에 오른쪽 나무..

후서역은 선좌자수, 후우자수, 마지막은 노드 자체이다

자나무의 범람 규칙이 같다

그는 중서가 두루 다니는 다음 노드를 찾아야 한다고 말했다.이 노드는 두 가지 상황으로 나눌 수 있다

이 노드에는 오른쪽 나무가 있다

이 노드에는 오른쪽 나무가 없다

첫 번째 비교 처리는 비교적 간단하다. 오른쪽 노드를 직접 중간 순서로 훑어보면 되고 훑어보는 가장 오른쪽 노드를 되돌려준다

두 번째 상황은 또 두 가지 상황으로 나뉜다.

이 노드는 부모 노드의 왼쪽 하위 노드이다

이 노드는 부모 노드의 오른쪽 하위 노드이다

여기서 이 노드는 부모 노드의 왼쪽 하위 노드이다. 이런 상황은 비교적 간단하기 때문에 부모 노드를 직접 되돌려주면 된다

만약에 아버지 노드의 오른쪽 노드라면 끊임없이 위로 이동해야 한다. 대응하는 노드가 아버지 노드의 오른쪽 노드(즉 왼쪽 노드)가 아닐 때까지 그는 아버지 노드의 왼쪽 노드이기 때문에 이 노드의 아버지 노드를 되돌려주면 되거나 뿌리 노드를 두루 돌아다니며null로 되돌려준다

그래서 진행 중에 옮겨다녀야 할 첫 번째 옮겨다니는 노드의 함수, 즉 위의 getNextNode를 도입해야 한다
이 코드는 주로 사고방식에 따라 분해되기 때문에 먼저 귀속으로 간단하게 실현했다.만약 다른 함수를 끼워 넣지 않는다면, while를 사용하여 해답을 구하면, 코드는 다음과 같이 간결할 것이다

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null){
            return null;
        }
        if(pNode.right != null){
            pNode = pNode.right;
            while(pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }
        while(pNode.next != null){
            if(pNode.next.left== pNode){
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }
}