This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card 39 days 🎈!
🚀 Algorithm 🚀

🌲 Example: Preorder traversal of a binary tree

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Example 1: 

Enter: root = [1,null,2.3] output: [1.2.3]
Copy the code

Example 2:

Input: root = [] Output: []Copy the code

Example 3:

Enter: root = [1] output: [1]
Copy the code

Example 4: 

Enter: root = [1.2] output: [1.2]
Copy the code

Example 5: 

Enter: root = [1.null.2] output: [1.2]
Copy the code

Tip:

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100

🌻C# method: recursion

Thinking analytical

The fast and slow Pointers start at the same time from the beginning of the node. The fast Pointers take two steps at a time, and the slow Pointers take one step at a time. If there is a loop, the fast Pointers catch up with the slow Pointers sooner or later.

Code:

public class Solution 
{
    private IList<int> res = new List<int> ();public IList<int> PreorderTraversal(TreeNode root) 
    {
        Traversal(root);
        return res;
    }

    private void Traversal(TreeNode node)
    {
        if(node! =null) { res.Add(node.val); PreorderTraversal(node.left); PreorderTraversal(node.right); }}}Copy the code

The execution result

By execution time:224Ms, in all C# beat 70.79% of users in submissionMemory consumption:29.8MB, in all CBeat 79.47% of users in # commit
Copy the code

🌻Java Method 1: Recursion

Thinking analytical

First we need to understand what binary tree traversal is: we traverse the tree in the same way as we traverse the root node — left subtree — right subtree, and we traverse the tree in the same way as we traverse the left subtree or right subtree until we traverse the entire tree.

Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Define preorder(root) to represent the answer currently traversed to the root node. By definition, we simply add the root value to the answer, recursively call preorder(root.left) to traverse the left subtree of root, and recursively call preorder(root.right) to traverse the right subtree of root. Recursion terminates when an empty node is encountered.

Code:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return; } res.add(root.val); preorder(root.left, res); preorder(root.right, res); }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.6MB, beat out all Java commits59.89% of the userCopy the code

Complexity analysis

Time complexity: O(n), where n is the number of nodes in the binary tree space complexity: O(n)Copy the code

🌻Java Method 1: Iterate

We can also implement the recursive function of method 1 iteratively. The two methods are equivalent, but the difference is that the recursive method implicitly maintains a stack.

We need to simulate the stack explicitly during iteration, and the rest of the implementation and details are the same, as shown in the code below

Code:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while(! stack.isEmpty() || node ! =null) {
            while(node ! =null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        returnres; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.9MB, beat out all Java commits5.45% of the userCopy the code

Complexity analysis

Time complexity: O(n), where n is the number of nodes in the binary tree space complexity: O(n)Copy the code

💬 summary

  • Today is the thirty-ninth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!