144. Binary Tree Preorder Traversal

먼저 두 갈래 나무를 훑어보는 것은 창고와 귀속 두 가지 방법이 있다. 창고(깊이 우선 두 갈래 나무를 훑어보는 것)

var preorderTraversal = function(root) {
    var res = [];
    if (root) {
        var s = [root];
        while(s.length!==0) {
            var temp = s.pop();
            res.push(temp.val);
            if (temp.right)
                s.push(temp.right);
            if (temp.left)
                s.push(temp.left);
        }
    }
    return res;
};

귀속:

var preorderTraversal = function(root) {
    var res = [];
    if (root) {
        var help = function(root) {
            res.push(root.val);
            if (root.left)
                help(root.left);
            if (root.right)
                help(root.right);
        }
        help(root);
    }
    return res;
};

94. Binary Tree Inorder Traversal

중간 순서로 두 갈래 트리를 옮겨다니면서 귀속을 사용하면 간단하게 해결 방안을 얻을 수 있어요.

var inorderTraversal = function(root) {
    var record = [];
    if (root) {
        var help = function(root) {
            if (root.left)
                help(root.left);
            record.push(root.val);
            if (root.right)
                help(root.right);
        };
        help(root);
    }
    return record;
};

만약 귀속되지 않고 창고를 사용한다면, 이렇게 하면 약간의 처리가 필요하다. 현재 노드에 대해 말하자면, 만약 왼쪽 노드가 있다면, 현재 노드가 현재 두루 돌아다녀야 할 노드가 아니라는 것을 의미한다. 창고에 눌러서 왼쪽 노드를 계속 찾는 것이다.만약에 나무에 왼쪽 노드가 있다면 우선, 지금 이 노드는 두루 돌아다니는 노드입니다. 노드 값을 결과 수조에 넣고, 이 노드가 오른쪽 노드가 있으면 오른쪽 노드를 창고에 눌러서 오른쪽 노드의 왼쪽 노드를 따라 아래로 찾습니다.

var inorderTraversal = function(root) {
    var res = [];
    if (root) {
        var s = [];
        s.push(root);
        var left = root.left;
        while(s.length!==0) {
            if (left!==null) {
                s.push(left);
                left = left.left;
            } else {
                var temp = s.pop();
                res.push(temp.val);
                if (temp.right){
                    s.push(temp.right);
                    left = temp.right.left;
                }
            }
        }
    }
    return res;
};

145. Binary Tree Postorder Traversal

두 갈래 트리를 차례로 훑어보는 것은 간단합니다.

var postorderTraversal = function(root) {
    var res = [];
    var help = function(root) {
        if (root.left) 
            help(root.left);
        if (root.right) 
            help(root.right);
        res.push(root.val);
    };
    if (root) 
        help(root);
    return res;
};

창고를 사용하는 것은 중서적 반복과 차이가 많지 않은 사상이다. 현재 노드에 대해 말하자면 왼쪽 노드가 있다면 현재 노드가 현재 반복해야 할 노드가 아니라는 것을 의미한다. 창고에 눌러서 왼쪽 노드를 계속 찾는 것이다.만약에 나무에 왼쪽 노드가 있다면 창고 안의 마지막 원소를 찾아 오른쪽 노드가 있는지 확인하고 오른쪽 노드가 있으면 오른쪽 노드를 창고에 눌러서 이 노드를 표시하고 오른쪽 노드의 왼쪽 노드를 따라 아래로 찾아라.만약 창고 안의 마지막 원소가 하위 노드가 없다면 밖으로 튕겨야 한다. 만약에 이 노드가 왼쪽 노드라면 바로 튕겨내면 된다. 만약 오른쪽 노드라면 튕겨서 아버지 노드를 튀겨내야 한다.

var postorderTraversal = function(root) {
    var res = [];
    if (root) {
        var s = [root];
        var left = root.left;
        while(s.length!==0) {
            if (left) {
                s.push(left);
                left = left.left;
            } else {
                var temp = s[s.length - 1];
                if (temp.right) {
                    temp.right.flag = true;
                    s.push(temp.right);
                    left = temp.right.left;
                } else {
                    temp = s.pop();
                    while (temp.flag) {
                        res.push(temp.val);
                        temp = s.pop();
                    }
                    res.push(temp.val);
                }
            }
        }
    }
    return res;
};