I can flip binary trees. Does Google still want me?

Preface explains

Algorithm learning, daily brush record.

Subject to connect

Flip the binary tree

The subject content

Flip a binary tree.

Example:

Input:

Output:

Remark:

This question was inspired by Max Howell’s original question:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t flip a binary tree on a whiteboard during an interview. That’s too bad.

The analysis process

Flipping a binary tree is easy and can be done recursively.

Think of the binary tree as the whole of the root, the left child, and the right child, and flip the left child and the right child of the root.

If the left and right children are trees, the recursion continues the same way until the left and right children are empty, and the recursion begins to backtrack.

Finally, the root node of the binary tree is returned, which is the flipped binary tree.

To solve the code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */ class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) { Return null; } // Using recursion, treat the tree as the whole of the root node, the left child, and the right child, and completely reverse the left child and the right child of the root node. If the left child and the right child are also trees, then do the same recursion until the left child and the right child are empty. TreeNode left = invertTree(root.left); Root. left = invertTree(root.right); root.right = left; // Return the flipped root node. }}Copy the code

Submit the results

It took 0ms to execute, beating 100.00% user time, 35.9MB memory consumption, and 37.33% user space.

It turns out that flipping binary trees is so easy, I can flip binary trees, Google still want me?

Extension analysis

However, I will write the complete code, the above is obviously not the complete code, when we run, the input is an array, the output is also an array, as shown in the figure:

InvertTree: invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode invertTree: TreeNode But if we want to write the whole code ourselves, we need to do the transformation ourselves.

Here, only one array is given to determine the binary tree, which proves to be sequential traversal, because the pre-order traversal, middle-order traversal, post-order traversal can not be derived from a single array of binary tree, sequential traversal can be derived from a single array of binary tree.

Sequential traversal: Layer by layer from top to bottom, each layer from left to right to access all nodes.

For easy understanding, here are some examples:

Input array 1: [0, NULL,2, NULL,4, NULL,6]

Output binary tree 1:

Input array 2: [1, NULL,2,3]

Output binary tree 2:

Input array 3: [0,1,null,null,4]

Output binary tree 3:

Input array 4: [4,2,7,1,3,6,9]

Output binary tree 4:

Array to binary tree: It is a little strange that I have read a lot of algorithm books and looked up a lot of online materials, but I rarely see any mention of how to convert a hierarchical traversal array into a binary tree. Here I put together a conversion method, see the complete code at the back of the arrayToTreeNode method, which implements breadth-first search through queue assistance. That is to simulate the sequence traversal process from top to bottom from left to right, the array is converted into a binary tree, pay attention to the array element is null, when the array element is null, the node has no children, but it will occupy an array element.

Binary tree to array: The treeNodeToArray method implements breadth-first search through queue assistance, which is to simulate the sequence traversal process from top to bottom from left to right. First, the binary tree is converted into a two-layer List. Each layer of the two-layer List stores the left-to-right node values of the tree. If all elements in a row are null, then this row is not null. If the last element in a row is null, the last element is removed.

The complete code is as follows:

import java.util.*; Public class Main {public static void Main (String[] args) {// Get the input result Scanner Scanner = new Scanner(system.in); String str = scanner.next(); scanner.close(); Integer[] nums; If ("[]".equals(STR)) {// Nums = null; } else {/ / when the array is not null String [] STRS = STR. Split (" \ \ [") [1]. The split ("] ") [0]. The split (", "); int size = strs.length; nums = new Integer[size]; for (int i = 0; i < size; ++i) { if ("null".equals(strs[i])) { nums[i] = null; } else { nums[i] = Integer.parseInt(strs[i]); TreeNode root = arrayToTreeNode(nums); TreeNode result = invertTree(root); System.out.println(Arrays.toString(treeNodeToArray(result))); Private static TreeNode arrayToTreeNode(Integer[] nums) {// arrayToTreeNode(Integer[] nums) { // If the left child of the node is null and the right child is not null, then the next element of the array will start with the child of the right child, because the left child is null. No child nodes // Example: [0, null, 2, null, 4, null, 6], [1, null, 2, 3], [0, 1, null, null, 4]. ,2,7,1,3,6,9 [4] the if (nums = = null | | nums. Length = = 0) {/ / if a binary tree node is empty, direct return empty return null; } int I = 1; TreeNode root = new TreeNode(nums[0]); // define the current binary TreeNode, save the temporary value TreeNode current; // Define the value of the current array Integer value; Queue<TreeNode> Queue = new LinkedList<>(); Queue.add (root); While (I < nums.length) {current = queue.poll(); Value = nums[i++]; if (value ! TreeNode left = new TreeNode(value); TreeNode left = new TreeNode(value); if (current ! = null) {// Create the left child of the current binary tree node. } // Queue. Add (left); } if (I < nums.length) {value = nums[I ++]; if (value ! TreeNode right = new TreeNode(value); TreeNode right = new TreeNode(value); if (current ! = null) {// Construct the right child of the current binary tree. } // Queue. Add (right); }}} // Return root; } // The binary tree is converted into an array, and the hierarchy is traversed from top to bottom and from left to right, which requires special processing because it is a flipped binary tree. The last empty node should also be displayed as null. Private static Integer[] treeNodeToArray(TreeNode root) {// Define a list of two levels, List<List<Integer>> List = new ArrayList<>(); If (root == null) {// If the binary tree node is empty, return new Integer[0]; } // Through queue assistance, traversal from top to bottom of each layer, traversal at each layer, each traversal of a node, determine the two child nodes of the node, if not empty, put the child node behind the queue, queue to ensure that the tree traversal from top to bottom in accordance with the hierarchy. Queue<TreeNode> Queue = new LinkedList<>(); Queue.add (root); queue.add(root); While (queue.size() > 0) {List<Integer> temp = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); Int size = queue.size(); For (int I = 0; int I = 0; i < size; TreeNode node = queue.poll(); if (node ! = null) {// Add the value of the listed element to the inner list temp.add(node.val); if (node.left ! Queue.add (node.left); } else {queue. Add (null);} else {queue. Add (null); } if (node.right ! Queue.add (node.right); // Queue.add(node.right); } else {queue. Add (null);} else {queue. Add (null); }} else {// Add a null value to the inner list to accommodate the effect of flipping the binary tree temp.add(null); }} // Whether all elements of the inner list are empty Boolean isAllNull = true; For (Integer col: temp) {if (col! = null) {// If one element is not empty, then not all elements are empty. break; } } if (! List.add (temp); list.add(temp); list.add(temp); System.out.println("treeNodeToArray list:" + list); Int count = 0; For (List<Integer> row: List) {count += row.size(); } // Define array Integer[] nums = new Integer[count]; Int n = 0; For (List<Integer> row: List) {for (Integer col: row) {nums[n++] = col; }} if (nums[nums.length-1] == null) {// If (nums[nums.length-1] == null) {// If (nums[nums.length-1] == null) {// If (nums[nums.length-1] == null) { Return Array.copyof (nums, nums.length-1); } // return nums; } private static TreeNode invertTree(TreeNode root) {if (root == null) {return null; } // Using recursion, treat the tree as the whole of the root node, the left child, and the right child, and completely reverse the left child and the right child of the root node. If the left child and the right child are also trees, then do the same recursion until the left child and the right child are empty. TreeNode left = invertTree(root.left); Root. left = invertTree(root.right); root.right = left; // Return the flipped root node. }} class TreeNode {int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}Copy the code

Full code access: github.com/zjhpure/alg…

The original link

Flip the binary tree