이진트리 순회

Range Sum of BST - LeetCode

전위 순회

부모노드를 먼저 처리한 후에 자식노드를 처리해야 할때

후위 순회 

자식노드를 먼저 처리한 후에 부모노드를 처리해야 할때 (ex, 디렉토리 용량 계산)

/**
 * 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 answer = 0
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        guard let node = root else {
            return 0
        }
        dfs(node, low, high)
        return answer
    }
    
    func dfs(_ node: TreeNode, _ low:Int,_ high: Int) {
        if node.val >= low && node.val <= high {
            answer += node.val
        }
        // print(node.val) - 전위순회
        if let leftNode = node.left {
            dfs(leftNode, low, high)
        }
        // print(node.val) - 중위순회
        if let rightNode = node.right {
            dfs(rightNode, low, high)
        }
        // print(node.val) - 후위순회
    }
}

레벨 순회

같은 level의 노드 순회 (queue 이용)

Idea : root를 queue에 넣고 queue 가 empty 될때까지 순회

/**
 * 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 answer = 0
    var queue : [TreeNode] = []
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        guard let node = root else {
            return 0
        }
        queue.append(node)
        while !queue.isEmpty {
            let dequeueNode = queue.removeFirst()
            if dequeueNode.val >= low && dequeueNode.val <= high {
                answer += dequeueNode.val
            }
            if let leftNode = dequeueNode.left {
                queue.append(leftNode)
            }
            if let rightNode = dequeueNode.right {
                queue.append(rightNode)
            }
        }
        return answer
    }
}