JavaScript 및 Python에서 이진 트리 반전

유명하게도 Homebrew의 제작자는 화이트보드에서 이진 트리를 반전하지 못해 Google 인터뷰에서 떨어졌습니다. 구현해 보겠습니다. 이진 트리 반전에는 왼쪽에 있는 리프가 아닌 노드를 오른쪽에 있는 노드로 전환하는 작업이 포함됩니다.
아래 이미지는 프로세스를 간략하게 보여줍니다.
.

따라야 할 단계:-
  • 왼쪽 속성을 노드에 저장
  • 왼쪽 속성을 노드의 오른쪽 속성으로 설정
    3 오른쪽 속성을 저장된 왼쪽 속성으로 설정
  • 왼쪽 속성에서 InvertBinary를 재귀적으로 호출합니다.
    그런 다음 노드의 오른쪽 속성에 있습니다.
  • 트리를 반환합니다.

  • JavaScript의 코드 구현:-

    class Node{
        constructor(val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    
    class BST{
        constructor(){
            this.root = null;
        }
    
        insert(val){
            let newNode = new Node(val);
            if(!this.root){
                this.root = newNode;
            }else{
                let current = this.root;
                while(true){
                    if(val < current.val){
                        if(current.left === null){
                            current.left = newNode;
                            return this
                        }else{
                            current = current.left;
                        }
                    }else{
                        if(current.right === null){
                            current.right = newNode;
                            return this
                        }else{
                            current = current.right
                        }
                    }
                }
    
            }
    
        }
    
           DFSInOrder(){
            let data=[];
            function traverse(node){
                if(node.left) traverse(node.left);
                data.push(node.val);
                if(node.right) traverse(node.right);
            }
            traverse(this.root);
            return data;
    
        }
    
        IBT(){
            function Invert(node){
                if(node === null) return ;
                let temp = node.left;
                node.left = node.right;
                node.right = temp;
    
                Invert(node.left);
                Invert(node.right);
            }
            Invert(this.root)
            return this.DFSInOrder()
        }
    
    
    
    }
    
    let tree = new BST();
    tree.insert(100);
    tree.insert(200);
    tree.insert(150);
    tree.insert(80);
    tree.insert(90);
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(180);
    tree.insert(190);
    tree.DFSInOrder();
    tree.IBT();
    


    파이썬에서:-

    class Node:
        def __init__(self,val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BST:
        def __init__(self):
            self.root= None
    
        def insert(self, val):
             newNode = Node(val)
             if self.root == None:
                 self.root= newNode
             else:
                 current = self.root
                 while True:
                     if val< current.val:
                         if current.left == None:
                             current.left = newNode
                             return self
                         else:
                             current= current.left 
                     else:
                         if(current.right == None):
                             current.right = newNode
                             return self
                         else:
                             current = current.right
    
    
        def dfsInorder(self):
            data =[]
    
            def traverse(node):
                if(node.left): traverse(node.left)
                data.append(node.val)
                if(node.right): traverse(node.right)
            traverse(self.root)         
            return data
    
    
    
    
        def IBT(self):
            def InvertTree(node):
                if node == None: return 
    
                temp= node.left
                node.left = node.right
                node.right = temp
    
                InvertTree(node.left)
                InvertTree(node.right)
            InvertTree(self.root) 
    
            return self.dfsInorder()
    
    bst = BST()
    bst.insert(100)
    bst.insert(200)
    bst.insert(150)
    bst.insert(175)
    bst.insert(160)
    bst.insert(180)
    bst.insert(75)
    bst.insert(50)
    bst.insert(65)
    bst.insert(40)
    bst.insert(55)
    bst.insert(20)
    
    print(bst.dfsInorder())
    print(bst.IBT())
    
    


    좋은 주말 되세요.

    좋은 웹페이지 즐겨찾기