二叉树遍历

二叉树定义

二叉树定义代码

class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

普通前中后序遍历

前序遍历代码

//递归
void PreorderTraversal(TreeNode root)
{
    if (root != null)
    {
        Console.Write(root.val + " ");
        PreorderTraversal(root.left);
        PreorderTraversal(root.right);
    }
}
//迭代
void PreorderTraversal(TreeNode root)
{
    if (root == null)
    {
        return;
    }
    Stack stack = new Stack();
    stack.Push(root);
    while (stack.Count != 0)
    {
        TreeNode node = stack.Pop();
        Console.Write(node .val + " ");
        if (node.right != null)
        {
            stack.Push(node.right);
        }
        if (node.left != null)
        {
            stack.Push(node.left);
        }
    }
    return;
}

中序遍历代码

//递归
void MiddleTraversal(TreeNode root)
{
    if (root != null)
    {
        MiddleTraversal(root.left);
        Console.Write(root.val + " ");
        MiddleTraversal(root.right);
    }
}
//迭代
void InorderTraversal(TreeNode root)
{
    if (root == null)
    {
        return;
    }
    Stack stack = new Stack();
    while (stack.Count == 0 || root != null)
    {
        while (root != null)
        {
            stack.Push(root);
            root = root.left;
        }
        root = stack.Pop();
        Console.Write(root.val + " ");
        root = root.right;
    }
    return;
}

后序遍历代码

//递归
void SubsequentTraversal(TreeNode root)
{
    if (root != null)
    {
        SubsequentTraversal(root.left);
        SubsequentTraversal(root.right);
        Console.Write(root.val + " ");
    }
}
//迭代 -未处理结果，输出结果倒序一下即可
public IList PostorderTraversal(TreeNode root)
{
    if (root == null)
    {
        return;
    }
    Stack stack = new Stack();
    stack.Push(root);
    while(stack.Count != 0)
    {
        TreeNode node = stack.Pop();
        Console.Write(root.val + " ");
        if(node.left != null)
        {
            stack.Push(node.left);
        }

        if (node.right != null)
        {
            stack.Push(node.right);
        }
    }
    return;
}

层次遍历

BFS实现自上向下层次遍历

IList> LevelOrderBottom(TreeNode root)
{
    //存储最终结果
    IList> res = new List>();
    //创建队列
    Queue queue = new Queue();

    if(root != null)
    {
        queue.Enqueue(root);
    }
    
    while(queue.Count != 0)
    {
        //创建列表存储当前队列节点值
        IList nodes = new List();
        int queueCount = queue.Count;
        for(int i=0;i

//自底向上，每次在最前面新增
res.Insert(0,nodes);