Binary Tree Inorder Traversal

1187 단어
중서적 2차원 트리는 두 가지 방법으로 나뉘는데 첫 번째는 귀속법이고 두 번째는 교체법이다. 귀속법은 LeetCode OJ에서 trivial(중요하지 않음)이라고 불리기 때문에 교체법 2차원 트리에 중점을 둔다.
  • 귀속법
  • struct TreeNode {
        int value;
        TreeNode *leftTreeNode;
        TreeNode *rightTreeNode;
    };
    void traverseInOrder (TreeNode *treeNode) {
        if (treeNode != NULL) {
            traverseInOrder(treeNode->leftTreeNode);
            std::cout << treeNode->value;
            traverseInOrder(treeNode->rightTreeNode);
        }
    }
    
  • 교체법
  • struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
    };
    vector traverseInOrder (TreeNode *root) {
        vector allValueInOrder;
        TreeNode *currentNode = root;
        stack stack;
        while (currentNode || !stack.empty()) {// isEmpty YES, 
            if (currentNode) {
                stack.push(currentNode);
                currentNode = currentNode->left;
            } else {
                currentNode = stack.top();
                stack.pop();// pop void, pop 
                allValueInOrder.push_back(currentNode->val);
                currentNode = currentNode->right;
            }
        }
        return allValueInOrder;
    }
    

    좋은 웹페이지 즐겨찾기