XIAOSUO 记录个人学习的足迹

首先写一个二叉树的C#实现，这是我们的基石：

public class BinNode
{
    public int Element;
    public BinNode Left;
    public BinNode Right;
    public BinNode(int element, BinNode left, BinNode right)
    {
        this.Element = element;
        this.Left = left;
        this.Right = right;
    }
    
    public bool IsLeaf()
    {
        return this.Left == null && this.Right == null;
    }
}

一、怎样从顶部开始逐层打印二叉树结点数据

有2种算法：

算法1：基于Queue来实现，也就是广度优先搜索（BFS）的思想

static void PrintTree1(BinNode root)
{
    if (root == null) return;
    BinNode tmp = null;
    Queue queue = new Queue();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        tmp = (BinNode)queue.Dequeue();
        Console.WriteLine(tmp.Element);
        if (tmp.Left != null)
            queue.Enqueue(tmp.Left);
        if (tmp.Right != null)
            queue.Enqueue(tmp.Right);
    }
}

话说，BFS和DFS思想本来是用于图的，但我们不能被传统的思维方式所束缚。

算法2：基于单链表实现

如果没有Queue给我们用，我们只好使用单链表，把每个节点存在单链表的Data中，实现如下：

public class Link
{
    public Link Next;
    public BinNode Data;
    public Link(Link next, BinNode data)
    {
        this.Next = next;
        this.Data = data;
    }
}

看过了Queue的实现，我们发现永远是先出队1个（队头），然后入队2个（把出队的Left和Right放到队尾）。

对于单链表而言，我们可以先模拟入队——把first的Data所对应的Left和Right，先后插到second的后面，即second.Next和second.Next.Next位置，同时second向前走0、1或2次，再次到达链表末尾，这取决于Left和Right是否为空；然后我们模拟出队——first前进1步。

当first指针走不下去了，那么任务也就结束了。

static void PrintTree2(BinNode root)
{
    if (root == null) return;
    Link head = new Link(null, root);
    Link first = head;
    Link second = head;
    while (first != null)
    {
        if (first.Data.Left != null)
        {
            second.Next = new Link(null, first.Data.Left);
            second = second.Next;
        }
        if (first.Data.Right != null)
        {
            second.Next = new Link(null, first.Data.Right);
            second = second.Next;
        }
        Console.WriteLine(first.Data.Element);
        first = first.Next;
    }
}

二、设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。

算法1：做一个容器，我们在遍历二叉树寻找节点的同时，把从根到节点的路径扔进去（两个节点就是两个容器）。由于根节点最后一个被扔进去，但我们接下来又需要第一个就能访问到它——后进先出，所以这个容器是一个栈。时间复杂度O(N)，空间复杂度O(N)。

static bool GetPositionByNode(BinNode root, BinNode node, ref Stack stack)
{
    if (root == null)
        return false;
    if (root == node)
    {
        stack.Push(root);
        return true;
    }
    if (GetPositionByNode(root.Left, node, ref stack) || GetPositionByNode(root.Right, node, ref stack))
    {
        stack.Push(root);
        return true;
    }
    return false;
}

然后我们要同时弹出这两个容器的元素，直到它们不相等，那么之前那个相等的元素就是我们要求的父亲节点。

static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2)
{
    Stack stack1 = new Stack();
    GetPositionByNode(root, node1, ref stack1);
    Stack stack2 = new Stack();
    GetPositionByNode(root, node2, ref stack2);
    BinNode tempNode = null;
    while (stack1.Peek() == stack2.Peek())
    {
        tempNode = (BinNode)stack1.Pop();
        stack2.Pop();
    }
    return tempNode;
}

算法2：如果要求o(1)的空间复杂度，就是说，只能用一个变量来辅助我们。

我们选择一个64位的整数，然后从1开始，从左到右逐层为二叉树的每个元素赋值，root对应1，root.Left对应2，root.Right对应3，依次类推，而不管实际这个位置上是否有节点，我们发现两个规律：

//// 1

//// 2 3

//// 4 5 6 7

//// 8 9 10

如果要找的是5和9位置上的节点。

我们发现，它们的二进制分别是101和1001，右移1001使之与101位数相同，于是1001变成了100（也就是9的父亲4）。

这时101和100（也就是4和5位于同样的深度），我们从左往右找，101和100具有2位相同，即10，这就是我们要找的4和5的父亲，也就是9和5的最近父亲。

由上面观察，得到算法：

1)将找到的两个节点对应的数字

static bool GetPositionByNode(BinNode root, BinNode node, ref int pos)
{
    if (root == null)
        return false;
    if (root == node)
        return true;
    int temp = pos;
    //这么写很别扭，但是能保证只要找到就不再进行下去
    pos = temp * 2;
    if (GetPositionByNode(root.Left, node, ref pos))
    {
        return true;
    }
    else
    {
        //找不到左边找右边
        pos = temp * 2 + 1;
        return GetPositionByNode(root.Right, node, ref pos);
    }
}

2)它们的二进制表示，从左向右逐一比较，直到一个结束或不再相同，则最大的相同子串，就是我们需要得到的最近父亲所对应的位置K。

static int FindParentPosition(int larger, int smaller)
{
    if (larger == smaller) return larger;
    int left = GetLen(larger) - GetLen(smaller);
    while (left > 0)
    {
        larger = larger >> 1;
        left--;
    }
    while (larger != smaller)
    {
        larger = larger >> 1;
        smaller = smaller >> 1;
    }
    return smaller;
}
static int GetLen(int num)
{
    int length = 0;
    while (num != 0)
    {
        num = num >> 1;
        length++;
    }
    return length;
}

3)第3次递归遍历，寻找K所对应的节点。

函数GetNodeByPosition的思想是，先算出k在第几层power，观察k的二进制表示，比如说12，即1100，从左向右数第一个位1不算，还剩下100，1表示向右走，0表示向左走，于是从root出发，1->3->6->12。

static BinNode GetNodeByPosition(BinNode root, int num)
{
    if (num == 1) return root;
    int pow = (int)Math.Floor(Math.Log(num, 2)); //1 return 0, 2-3 return 1, 4-7 return 2
    //第一个位不算
    num -= 1 << pow;
    while (pow > 0)
    {
        if ((num & 1 << (pow - 1)) == 0)
            root = root.Left;
        else
            root = root.Right;
        pow--;
    }
    return root;
}

总结上面的3个步骤：

static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2)
{
    int pos1 = 1;
    GetPositionByNode(root, node1, ref pos1);
    int pos2 = 1;
    GetPositionByNode(root, node2, ref pos2);
    int parentposition = 0;
    if (pos1 >= pos2)
    {
        parentposition = FindParentPosition(pos1, pos2);
    }
    else //pos1<pos2
    {
        parentposition = FindParentPosition(pos2, pos1);
    }
    return GetNodeByPosition(root, parentposition);
}

三、如何不用递归实现二叉树的前序/后序/中序遍历

算法思想：三种算法的思想都是让root的Left的Left的Left全都入栈。所以第一个while循环的逻辑，都是相同的。

下面详细分析第2个while循环，这是一个出栈动作，只要栈不为空，就始终要弹出栈顶元素，由于我们之前入栈的都是Left节点，所以每次在出栈的时候，我们都要考虑Right节点是否存在。因为前序/后序/中序遍历顺序的不同，所以在具体的实现上有略为区别。

1)前序遍历

这个是最简单的。

前序遍历是root->root.Left->root.Right的顺序。

因为在第一个while循环中，每次进栈的都可以认为是一个root，所以我们直接打印，然后root.Right和root.Left先后进栈，那么出栈的时候，就能确保先左后右的顺序。

static void PreOrder(BinNode root)
{
    Stack stack = new Stack();
    BinNode temp = root;
    //入栈
    while (temp != null)
    {
        Console.WriteLine(temp.Element);
        if (temp.Right != null)
            stack.Push(temp.Right);
        temp = temp.Left;
    }
    //出栈，当然也有入栈
    while (stack.Count > 0)
    {
        temp = (BinNode)stack.Pop();
        Console.WriteLine(temp.Element);
        while (temp != null)
        {
            if (temp.Right != null)
                stack.Push(temp.Right);
            temp = temp.Left;
        }
    }
}

//后序遍历比较麻烦，需要记录上一个访问的节点，然后在本次循环中判断当前节点的Right或Left是否为上个节点，当前节点的Right为null表示没有右节点。

static void PostOrder(BinNode root)
{
    Stack stack = new Stack();
    BinNode temp = root;
    //入栈
    while (temp != null)
    {
        if (temp != null)
            stack.Push(temp);
        temp = temp.Left;
    }
    //出栈，当然也有入栈
    while (stack.Count > 0)
    {
        BinNode lastvisit = temp;
        temp = (BinNode)stack.Pop();
        if (temp.Right == null || temp.Right == lastvisit)
        {
            Console.WriteLine(temp.Element);
        }
        else if (temp.Left == lastvisit)
        {
            stack.Push(temp);
            temp = temp.Right;
            stack.Push(temp);
            while (temp != null)
            {
                if (temp.Left != null)
                    stack.Push(temp.Left);
                temp = temp.Left;
            }
        }
    }
}

//中序遍历，类似于前序遍历

static void InOrder(BinNode root)
{
    Stack stack = new Stack();
    BinNode temp = root;
    //入栈
    while (temp != null)
    {
        if (temp != null)
            stack.Push(temp);
        temp = temp.Left;
    }
    //出栈，当然也有入栈
    while (stack.Count > 0)
    {
        temp = (BinNode)stack.Pop();
        Console.WriteLine(temp.Element);
        if (temp.Right != null)
        {
            temp = temp.Right;
            stack.Push(temp);
            while (temp != null)
            {
                if (temp.Left != null)
                    stack.Push(temp.Left);
                temp = temp.Left;
            }
        }
    }
}

四、在二叉树中找出和为某一值的所有路径

算法思想：这道题目的苦恼在于，如果用递归，只能打出一条路径来，其它符合条件的路径打不出来。

为此，我们需要一个Stack，来保存访问过的节点，即在对该节点的递归前让其进栈，对该节点的递归结束后，再让其出栈——深度优先原则（DFS）。

此外，在递归中，如果发现某节点（及其路径）符合条件，如何从头到尾打印是比较头疼的，因为DFS使用的是stack而不是queue，为此我们需要一个临时栈，来辅助打印。

static void FindBinNode(BinNode root, int sum, Stack stack)
{
    if (root == null)
        return;
    stack.Push(root.Element);
    //Leaf
    if (root.IsLeaf())
    {
        if (root.Element == sum)
        {
            Stack tempStack = new Stack();
            while (stack.Count > 0)
            {
                tempStack.Push(stack.Pop());
            }
            while (tempStack.Count > 0)
            {
                Console.WriteLine(tempStack.Peek());
                stack.Push(tempStack.Pop());
            }
            Console.WriteLine();
        }
    }
    if (root.Left != null)
        FindBinNode(root.Left, sum - root.Element, stack);
    if (root.Right != null)
        FindBinNode(root.Right, sum - root.Element, stack);
    stack.Pop();
}