면접 문제 (8) 두 갈래 나무의 다음 노드

제목: 두 갈래 나무와 그 중의 한 노드를 정하고 어떻게 중서가 서열을 훑어보는 다음 노드를 찾습니까?트리의 노드에는 좌우 하위 노드를 가리키는 두 개의 바늘이 있고 부모 노드를 가리키는 바늘이 있습니다.트리 노드의 정의:
    class TreeNode{
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        int val;
    }

사고방식: 구체적인 두 갈래 트리를 그려서 분석하면 알 수 있듯이 중서 역행 서열 중의 한 노드의 다음 노드의 위치는 이 노드가 오른쪽 노드에 영향을 받는지 여부이다. 만약에 이 노드가 오른쪽 노드가 존재한다면 다음 노드는 오른쪽 노드 중의 가장 왼쪽 노드이다.오른쪽 하위 트리가 존재하지 않으면 이 노드를 따라 위로 옮겨야 한다. 첫 번째가 부모 노드의 왼쪽 하위 노드인 것을 발견할 때까지 이 노드의 아버지 노드는 중차 옮겨다니는 서열의 다음 노드이다.
코드:
public TreeNode findNextInInSeq(TreeNode root, TreeNode node){
        if(root == null || node == null)
            return null;

        // 
        if(node.right == null){
            while(node.parent != null && node == node.parent.right)
                node = node.parent;
            return node.parent;
        }

        TreeNode right = node.right;
        while(right.left != null)
            right = right.left;
        return right;
    }

좋은 웹페이지 즐겨찾기