Dare2Solve
The problem involves performing a preorder traversal of a binary tree. In a preorder traversal, the nodes are visited in the following order: root, left subtree, and then right subtree. The task is to return the list of node values in the order they are visited.
Preorder traversal can be thought of as the process of visiting a node before its children. This order is naturally recursive because at each node, we perform the same operation: visit the node, traverse the left subtree, and then traverse the right subtree. The recursive nature of trees makes recursion an intuitive way to solve this problem.
Recursive Function:
preOrder
that takes the current node and a list res
as arguments.null
, return immediately.res
.preOrder
function on the left child, then on the right child.Initialization:
res
that will store the node values in preorder.preOrder
function with the root of the tree and the list res
.res
which contains the preorder traversal of the tree.(O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the traversal.
res
, which contains the node values.
class Solution {
public:
void preOrder(TreeNode* root, std::vector<int>& res) {
if (root == nullptr) return;
res.push_back(root->val);
preOrder(root->left, res);
preOrder(root->right, res);
}
std::vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
preOrder(root, res);
return res;
}
};
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def preOrder(self, root, res):
if not root:
return
res.append(root.val)
self.preOrder(root.left, res)
self.preOrder(root.right, res)
def preorderTraversal(self, root):
res = []
self.preOrder(root, res)
return res
/*class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
*/
class Solution {
private void preOrder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root, res);
return res;
}
}
function preOrder (root, res) {
if(root == null) return;
else res.push(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
};
var preorderTraversal = function(root) {
let res = [];
preOrder(root, res);
return res;
};