了解过二叉树就应该知道,二叉树存在三种遍历方法:前序遍历(根→左→右)、中序遍历(左→根→右)、后续遍历(左→右→根)。
自定义二叉树:
/// <summary>
/// 二叉树的节点定义
/// </summary>
/// <typeparam name="T">数据具体类型</typeparam>
public class Node<T>
{
public T data { get; set; }
public Node<T> lchild { get; set; }
public Node<T> rchild { get; set; }
public Node()
{
}
public Node(T data)
{
this.data = data;
}
public Node(T data, Node<T> lchild, Node<T> rchild)
{
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
}
看一下三种遍历的代码实现:这里涉及到双递归的方法。
//该方法为递归遍历,仅阐述一下方法,目的在于搞清楚他们之间的逻辑关系。
// 前序遍历
public void PreOrder(Node<T> node)
{
//根节点开始,不为空的话,执行下面代码。
if (node != null)
{
// 前序方向根->左->右
//输出跟节点,往下走。
Console.Write(node.data + " ");
//当左节点不为空,返回递归。左节点为空,往下走
PreOrder(node.lchild);
//当左节点为空,输入右节点递归。
PreOrder(node.rchild);
}
}
// 中序遍历
public void MidOrder(Node<T> node)
{
if (node != null)
{
// 中序遍历方向,左->根->右
// 输入跟节点,左节点不为空,一直往下走,当左节点为空,输出最下面的左节点
MidOrder(node.lchild);
//输出
Console.Write(node.data + " ");
// 当每次输出一个左节点,如果他有右节点,递归右节点
MidOrder(node.rchild);
}
}
// 后序遍历
public void PostOrder(Node<T> node)
{
if (node != null)
{
//后序遍历,左->右->根
//一直递归左节点不输出,直到最下面的左右节点都市空的,才输出
PostOrder(node.lchild);
PostOrder(node.rchild);
//输出
Console.Write(node.data + " ");
}
}
解释一下双递归:(遇到双递归问题时,当第一个递归执行的时候,第二个递归并不是不执行,而是先进栈,根据顺序来,简单明了的解释就是,第一个递归你该怎么走就怎么走,完全没什么可以阻挡你,第二个递归就不同了,他是在第一个递归的基础上执行的,但不是立刻执行,而是执行递归进栈,当第一个递归完全执行技术的时候,第二个递归出栈,开始慢慢执行!)
具体解释:
如上图所示,二叉树的基本遍历方法中并不存在题目要求的方法,因此,必须自定义一种方法实现要求。
经过思考,得出如下步骤:
(1)定义两个链表,一个作为寄存链表,一个用作与最后输出的链表。
(2)若根节点不为空,把根节点存在寄存链表里。
(3)接下来,把他放到最后输出的链表里,之后呢,如果这个节点还有左右子节点的话,把左右子节点依次存在寄存链表里面。
(4)执行(3)循环,当循环执行次数大于或者等于寄存链表的长度时,停止执行(因为每执行一次循环,就相当于把寄存链表里的数字存到输出链表里,当全搞定,自然停止。)
using System.Collections.Generic;
/*
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode (int x)
{
val = x;
}
}*/
class Solution
{
public List<int> PrintFromTopToBottom(TreeNode root)
{
// write code here
//定义输出链表List1和寄存链表List2
List<int> List1 = new List<int>();
List<TreeNode> List2 = new List<TreeNode>();
int i = 0;
//根节点的添加方法
if (root != null)
{
List2.Add(root);
}
//(3)循环
while (i < List2.Count)
{
//定义一个节点Node1等于寄存链表中的第i个数
TreeNode Node1 = List2[i];
//给输出链表添加数据
List1.Add(Node1.val);
//左右子节点排队进入链表List2
if (Node1.left != null)
{
List2.Add(Node1.left);
}
if (Node1.right != null)
{
List2.Add(Node1.right);
}
//i的执行次数应等于二叉树节点数
i++;
}
return List1;
}
}