Tree

今天來複習一下常見遍歷樹的方式。 Recursive way Inorder traversal 先拜訪 left subtree，再依序拜訪 root node 跟 right subtree。 void Inorder_traversal(TreeNode *node){ if (node == NULL){ return; } Inorder_traversal(node->left); cout << node->val << " "; Inorder_traversal(node->rihgt); return; } Preorder traversal 先拜訪 root node，再依序拜訪 left subtree 跟 right subtree。 void Preorder_traversal(TreeNode *node){ if (node == NULL){ return; } cout << node->val << " "; Preorder_traversal(node->left); Preorder_traversal(node->rihgt); return; } Postorder traversal 先依序拜訪 left subtree 跟 right subtree，再拜訪 root node。 void Postorder_traversal(TreeNode *node){ if (node == NULL){ return; } Postorder_traversal(node->left); Postorder_traversal(node->rihgt); cout << node->val << " "; return; } 可以看到用 recursive 寫的話，三種方式的 code 基本上長一樣，而且複雜度也都一樣，只是差在遍歷 root node 的時間不一樣。 time complexity: $O(n)$ space complextiy: $O(h)$, where $h = $ tree height ...