二叉树先遍历c#版本
常用遍历方法:
- void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树
- void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树
- void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
- void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右
先明白入参和出参,可以在ide中测试 。
以下采用迭代和递归两种实现方法 。
定义树节点
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
输入1,null, 2, 3 , 数据结构如下
TreeNode node3 = new TreeNode(3);
TreeNode node2 = new TreeNode(2);
node2.left = node3;
TreeNode node1 = new TreeNode(1);
node1.right = node2;
方法实现1
采用迭代方法实现 ,先把node加入堆栈, 然后whild循环判断 ,如果有值的情况下,让节点出栈,出时加入返回的list列表, 然后再循环节点的左右节点,重新再加入栈,然后再出栈,加入列表,一直到堆栈列表为空。返回lint列表
public static IList<int> PreorderTraversal2(TreeNode root)
{
var list = new List<int>();
if (root == null) return null;
Stack<TreeNode> snodes=new Stack<TreeNode>();
snodes.Push(root);
while(snodes.Any())
{
TreeNode node = snodes.Pop();
list.Add(node.val);
if(node.right!=null) snodes.Push(node.right);
if (node.left != null) snodes.Push(node.left);
}
return list;
}
方法实现2
采用递归方法 ,利用yield特性返回节点值 。
public static IList<int> PreorderTraversal(TreeNode root)
{
var list = new List<int>();
if (root != null)
list = PreorderTraversalHelper(root).ToList();
return list;
}
private static IEnumerable<int> PreorderTraversalHelper(TreeNode node)
{
yield return node.val;
if (node.left != null)
foreach (var nod in PreorderTraversalHelper(node.left))
yield return nod;
if (node.right != null)
foreach (var nod in PreorderTraversalHelper(node.right))
yield return nod;
}
测试调用与输入输出
public static IList<int> PreorderTraversal2(TreeNode root)
{
var list = new List<int>();
if (root == null) return null;
Stack<TreeNode> snodes=new Stack<TreeNode>();
snodes.Push(root);
while(snodes.Any())
{
TreeNode node = snodes.Pop();
list.Add(node.val);
if(node.right!=null) snodes.Push(node.right);
if (node.left != null) snodes.Push(node.left);
}
return list;
}
还不快抢沙发