증가하는 주문 검색 트리

3491 단어 javascriptleetcode
이진 검색 트리의 루트가 주어지면 트리의 가장 왼쪽 노드가 이제 트리의 루트가 되고 모든 노드에 왼쪽 자식이 없고 오른쪽 자식이 하나만 있도록 트리를 순서대로 재정렬합니다.

예 1:

입력: 루트 = [5,3,6,2,4,null,8,1,null,null,null,7,9]
출력: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function(root) {
    let nodes = []
    dfs(root)

    let treeNode = new TreeNode(0)
    let current = treeNode
    for(let i = 0; i < nodes.length; i++) {
        current.right = new TreeNode(nodes[i])
        current = current.right
    }

    return treeNode.right

    function dfs(root) {
        if(root != null) {
            dfs(root.left)
            nodes.push(root.val)
            dfs(root.right)
        }
    }   
};

좋은 웹페이지 즐겨찾기