Preorder traversal of a binary tree

Given the root node of the binary tree, return the pre-order traversal of its node values.

See the LeetCode website for an example.

Source: LeetCode Link:… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: Recursion

Initialize a result set result, then recursively process it in the following order:

  • First, place the root node’s value in result.
  • Then put the processing result of root node’s left subtree into result;
  • Finally, put the processing result of the right subtree of root node into result;
  • When root is empty, an empty result is returned.

Finally, the result set Result is returned, which is the preorder traversal result of the tree.

Note: It is similar to the middle order traversal process, refer to the middle order traversal of leetcode-094 – binary tree.

import java.util.ArrayList; import java.util.List; public class LeetCode_144 { public static List<Integer> preorderTraversal(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> result = new ArrayList<>(); result.add(root.val); result.addAll(preorderTraversal(root.left)); result.addAll(preorderTraversal(root.right)); return result; } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.right = new TreeNode(2); root.right.left = new TreeNode(3); for (Integer integer : preorderTraversal(root)) { System.out.print(integer + " "); }}}

【 Daily Message 】
Every morning, remember to tell yourself: there is no miracle in this world, only your own efforts track; There is no luck in this world, only the courage to persevere.