Intermediate order traversal of a binary tree

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

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl… 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:

  • Firstly, the processing result of root node’s left subtree is placed in result.
  • Then place the root node’s value in 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, that is, the middle-order traversal result of the tree.

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

【 Daily Message 】
Give yourself a hope every day, try not to worry about tomorrow, not for yesterday and sigh, only for today is better.