BinaryTree_LeetCode_105. Construct Binary Tree from Preorder and Inorder Traversal [swift]

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

1. preorder의 element를 꺼내가며 순서대로 tree를 채워나간다.
2. 꺼낸 element를 ancestor node의 좌측 혹은 우측 node에 할당한다.
3. inorder를 꺼낸 값을 기준하여 분리하여 전달한다.

정답코드

17msBeats56.12%

55.73MBBeats50.51%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    var root: TreeNode?
    var _preorder = [Int]()
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        _preorder = preorder
        guard _preorder.count > 1 else { return TreeNode(preorder.first!) }
        let rootValue = _preorder.removeFirst()
        root = TreeNode(rootValue)

        let target = inorder.firstIndex(of: rootValue)!
        let lhs = target > 0 ? Array(inorder[0...(target-1)]) : [] // 기준의 좌측 tree
        let rhs = target + 1 > inorder.count ? [] : Array(inorder[(target+1)...]) // 기준의 우측 tree
        // print(lhs,rhs)
        
        divideNFind(root!, lhs, true)
        divideNFind(root!, rhs, false)
        
        return root
    }

    func divideNFind(_ ancestor: TreeNode, _ inorder: [Int], _ isLeft: Bool) {
        guard let rootValue = _preorder.first else { return }
        
        guard let target = inorder.firstIndex(of: rootValue) else { 
            // print("here?\(ancestor.val) \(rootValue) \(inorder)")
            return 
        }
        _preorder.removeFirst()
        let current = TreeNode(rootValue)
        if isLeft {
            ancestor.left = current
        } else {
            ancestor.right = current
        }
        // print(ancestor.val, current.val, _preorder, inorder)
        
        
        let lhs = target > 0 ? Array(inorder[0...(target-1)]) : [] // 기준의 좌측 tree
        let rhs = target + 1 > inorder.count ? [] : Array(inorder[(target+1)...]) // 기준의 우측 tree
        
        divideNFind(current, lhs, true)
        divideNFind(current, rhs, false)
        
    }

}

 

모범답안

추후에 다시 공부해보자.. 어렵네,,,

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        var (i, j) = (0, 0)
        let dummyHead = TreeNode(-3001)
        var stack = [dummyHead]
        var visited: Set<Int> = []
        var hasBranchStopped = false

        for i in 0..<preorder.count {
            while visited.contains(inorder[j]) {
                var last: TreeNode?
                while last?.val != inorder[j] {
                    last = stack.popLast()
                }

                if let last {
                    stack.append(last)
                    j += 1
                }
            }

            let node = TreeNode(preorder[i])
            
            if stack.last?.left == nil && !hasBranchStopped {
                stack.last?.left = node
            } else {
                hasBranchStopped = false
                stack.last?.right = node
            }
            
            stack.append(node)
            visited.insert(preorder[i])

            if preorder[i] == inorder[j] {
                hasBranchStopped = true
                var last: TreeNode?
                while j < inorder.count, stack.last?.val == inorder[j] {
                    j += 1
                    last = stack.popLast()
                }

                if let last {
                    stack.append(last)
                }
            }
        }

        return dummyHead.left
    }
}