Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

📢 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 25th day 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given the root node of a binary tree, return its middle-order traversal.

Example 1:

Enter: root = [1.null.2.3] output: [1.3.2]

Copy the code
The sample2Input: root = [] Output: []Copy the code
The sample3: Enter: root = [1] output: [1]
Copy the code

Example 4:

Enter: root = [1.2] output: [2.1]
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 ultimate goal is the middle order traversal of the binary tree

Middle order traversal of binary trees: traversal of the tree in the same way that we visit the left subtree — root node — right subtree, and traversal of the left or right subtree in the same way until we have traversed the entire tree.

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

Code:

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        List<int> list = new List<int> (); function(root);return list;
        void function(TreeNode root)
        {
            if(root==null)
                return ;
            if (root.left == null)
            {
                list.Add(root.val);
                function(root.right);// Find the right node when the left node does not exist and is already inserted
                return;
            }
            function(root.left); // Find the node to the left of root first
            list.Add(root.val);  // Insert root itself
            function(root.right);// Finally find the node to the right of root}}}Copy the code

The execution result

By execution time:220Ms, in all C# beat 87.01% of users in submissionMemory consumption:30.7MB, in all CBeat 5.29% of users in # commit
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java Method 1: Recursion

First we need to understand what middle order traversal of a binary tree is: we traverse the tree in the same way as we traverse the left subtree — the root node — the right subtree. We traverse the tree in the same way as we traverse the left subtree or the 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 inorder(root) to represent the answer currently traversed to root, so by definition we simply recursively call inorder(root.left) to traverse the left subtree of root, and then add the value of root to the answer. Recursively call inorder(root.right) to traverse the right subtree of the root node. The recursion terminates when an empty node is encountered.

Code:

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

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); }}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.24% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(n)Copy the code

🌻Java Method 2: dual Pointers

Thinking analytical

The recursive function of method 1 can also be implemented by iteration. The two methods are equivalent, but the difference is that the recursion implicitly maintains a stack, while we need to simulate the stack explicitly during iteration. Other things are the same.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i ! = m + n; ++i) { nums1[i] = sorted[i]; }}}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100% user memory consumption:36.8MB, beat out all Java commits13.83% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(n)Copy the code

💬 summary

  • Today is the 25th day of buckle algorithm 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!