1. Description

Invert a binary tree.

2. Runtime Distribution

3. Submission Details

4. Example

4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public TreeNode invertTree(TreeNode root) {
	if (root == null) {
		return root;
	}

	TreeNode tmp = invertTree(root.left);
	root.left = invertTree(root.right);
	root.right = tmp;

	return root;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class LeetCode0226 {

	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return root;
		}

		TreeNode tmp = invertTree(root.left);
		root.left = invertTree(root.right);
		root.right = tmp;

		return root;
	}

	public static void main(String[] args) throws IOException {
		LeetCode0226 leetcode = new LeetCode0226();

		TreeNode root = TreeNode.stringToTreeNode("[1, 3, null]");

		TreeNode ret = leetcode.invertTree(root);

		String out = TreeNode.treeNodeToString(ret);

		System.out.println(out);
	}

	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		static TreeNode stringToTreeNode(String input) {
			input = input.trim();
			input = input.substring(1, input.length() - 1);
			if (input.length() == 0) {
				return null;
			}

			String[] parts = input.split(",");
			String item = parts[0];
			TreeNode root = new TreeNode(Integer.parseInt(item));
			Queue nodeQueue = new LinkedList<>();
			nodeQueue.add(root);

			int index = 1;
			while (!nodeQueue.isEmpty()) {
				TreeNode node = nodeQueue.remove();

				if (index == parts.length) {
					break;
				}

				item = parts[index++];
				item = item.trim();
				if (!item.equals("null")) {
					int leftNumber = Integer.parseInt(item);
					node.left = new TreeNode(leftNumber);
					nodeQueue.add(node.left);
				}

				if (index == parts.length) {
					break;
				}

				item = parts[index++];
				item = item.trim();
				if (!item.equals("null")) {
					int rightNumber = Integer.parseInt(item);
					node.right = new TreeNode(rightNumber);
					nodeQueue.add(node.right);
				}
			}
			return root;
		}

		static String treeNodeToString(TreeNode root) {
			String output = "";
			Queue nodeQueue = new LinkedList<>();
			nodeQueue.add(root);
			while (!nodeQueue.isEmpty()) {
				TreeNode node = nodeQueue.remove();

				if (node == null) {
					output += "null, ";
					continue;
				}

				output += String.valueOf(node.val) + ", ";
				nodeQueue.add(node.left);
				nodeQueue.add(node.right);
			}
			return "[" + output.substring(0, output.length() - 2) + "]";
		}
	}
}

[/restab]
[/restabs]