Epoch

題目

  Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree [1, null, 2, 3]

   1
    \
     2
    /
   3

return [1, 3, 2]

Note: Recursive solution is trival, could you do it iteratively?

想法

  遞迴實作相對容易，inorder (中序)，LVR，先檢查左孩子，有就往左走，走到底後印出，在檢查右孩子，如此遞迴，即可求解。

recursive code

int rsize = 0;
int treesize(struct TreeNode* root) {
    if (root == NULL)
        return 0;
    else
        return (treesize(root->left)+treesize(root->right)+1);
    
}
void inorder(struct TreeNode* CurrentNode, int* rt) {
    if (CurrentNode) {
        inorder(CurrentNode->left, rt);
        rt[rsize]=CurrentNode->val;
        rsize++;
        inorder(CurrentNode->right, rt);
    }
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = treesize(root);
    int *rt = malloc((size+1)*sizeof(int));
    rsize = 0;
    inorder(root, rt);
    *returnSize = size;
    return rt;
}

嘗試看看 iterative 的作法

想法

  需用 stck 來 implement，所以改用 C++，有 STL 比較方便。首先不斷的往左孩子前進，都丟進 stack 中，走到底後，就開始 pop，並往右走一步，之後再重複不斷往左走，重複此步驟。

code

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode *>s;
        TreeNode *CurrentNode = root;
        while(1) {
            while(CurrentNode) {
                s.push(CurrentNode);
                CurrentNode = CurrentNode->left;
            }
            if(!s.empty()) {
                CurrentNode = s.top();
                cout << CurrentNode->val << endl;
                v.push_back(CurrentNode->val);
                s.pop();
                CurrentNode = CurrentNode->right;
            }
            else
                break;
            
        }
        return v;
    }
};