1/14/21 Binary Tree

Binary Tree란 

자료 구조의 한 종류인 Tree와 트리의 일종인 이진 트리(Binary Tree)

* Tree

잎새노드(leaf node)란 자식노드가 없는 노드입니다. internal node란 잎새노드를 제외한 노드를 나타냅니다. 루트노드(root node)란 부모노드가 없는 노드를 가리킵니다.

트리의 속성 중 가장 중요한 것이 ‘루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다’는 것입니다. 이 속성 때문에 트리는 다음 성질을 만족합니다.

• 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
• 회로(cycle)가 존재하지 않는다.
• 모든 노드는 서로 연결되어 있다.
• 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
• 엣지(edge)의 수 |EE| 는 노드의 수 |VV|에서 1을 뺀 것과 같다.

*Binary Tree

이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다. 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.

정이진트리는 다음 그림과 같습니다. 모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리입니다.

 

문제

 

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

 

Example 1:

 

Input: tree = [7,4,3,null,null,6,19], target = 3 Output: 3 Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

 

*
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val; // 노드의 값
 *     TreeNode left; // 왼쪽 자식 노드
 *     TreeNode right; // 오른쪽 자식노드
 *     TreeNode(int x) { val = x; }
 * }

 

 

How to Traverse the Tree: DFS(깊이우선탐색 Depth-First Searh) vs BFS(너비우선검색 Breadth-First Search)

BFS traverses level by level, and DFS first goes to the leaves.

 

*이진트리순회

순회의 종류는 세가지가 존재한다

 

1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

전위 순회 Preorder Traversal

root -> left -> right

부모노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

 

8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

중위 순회 Inorder Traversal

left -> root -> right

왼쪽 자식 노드  -> 부모노드 -> 오른쪽 자식 노드

 

 

8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

후위 순회 Postorder Traversal

left -> right -> root

왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모노드 

1) Recursive Inorder Traversal

class Solution {
    TreeNode ans, target;
    
    public void inorder(TreeNode o, TreeNode c) {
        if (o != null) {
            inorder(o.left, c.left);
            if (o == target) {
                ans = c;    
            }
            inorder(o.right, c.right);    
        }
    }
    
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        this.target = target;
        inorder(original, cloned);
        return ans;
    }
}

 

• Time complexity: \mathcal{O}(N)O(N) since one has to visit each node, where NN is a number of nodes.

• Space complexity: up to \mathcal{O}(H)O(H) to keep the recursion stack, where HH is a tree height.

2) Interative Inorder Traversal (Don't use Stack in Java, use ArrayDeque instead.)

 

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Deque<TreeNode> stack_o = new ArrayDeque();
        Deque<TreeNode> stack_c = new ArrayDeque();
        TreeNode node_o = original, node_c = cloned;

        while (!stack_o.isEmpty() || node_o != null) {
            while (node_o != null) {
                stack_o.add(node_o);
                stack_c.add(node_c);

                node_o = node_o.left;
                node_c = node_c.left;
            }
            node_o = stack_o.removeLast();
            node_c = stack_c.removeLast();
            if (node_o == target) {
                return node_c;
            }
            node_o = node_o.right;
            node_c = node_c.right;
        }
        return null;
    }
}

• Time complexity: \mathcal{O}(N)O(N) since one has to visit each node.

• Space complexity: up to \mathcal{O}(H)O(H) to keep the stack, where HH is a tree height.

**

why don't use Stack in Java, use ArrayDeque instead?

 

The reason has been included in the solution, you can click on the blue text "Don't use Stack in Java, use ArrayDeque instead". It leads you to the Oracle JavaDoc (https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html). In a word, Stack extends the class Vector and is inconsistent with what a stack should actually do. (For example, Stack allows you to access an element by index.) More info can be found in https://stackoverflow.com/questions/12524826/why-should-i-use-deque-over-stack