How to invert a binary tree
Given a binary tree. Write a method to
invertthistree
/* Definition for TreeNode
public class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
}
}
*/
public sealed class Solution
{
public TreeNode Invert(TreeNode root)
{
}
}
Example
Approach
For inverting a tree we need to swap child nodes for any node. In our example, first of all, we need to swap child nodes for node 1
Step 1
Step 2
then swap child nodes for node 3
Step 3
and finally, swap child nodes for node 2.
This approach can be easily implemented through breadth-first search.
Code
public TreeNode Invert(TreeNode root)
{
if (root == null)
{
return null;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count != 0)
{
TreeNode node = queue.Dequeue();
if (node == null)
{
continue;
}
TreeNode dummy = node.Left;
node.Left = node.Right;
node.Right = dummy;
queue.Enqueue(node.Left);
queue.Enqueue(node.Right);
}
return root;
}
Video Lesson
Recent articles
Nice to read
