找二叉树中给定元素的的左孩子结点_[二叉树面试算法]（一）之二叉树的遍历总结(4题)...

关于树的几个概念

完全二叉树：若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。

和完全二叉树相关的结论：

• 高度为h的满二叉树，其节点数为(2^h -1)。
• 高度为h的完全二叉树，其节点数范围是为[ 2^(h-1) ， (2^h -1) ].

满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。

哈夫曼树：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

二叉排序树：又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，

• 或者是具有下列性质的二叉树：
  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  • 左、右子树也分别为二叉排序树；
  • 没有键值相等的节点

二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找）

平衡二叉树：又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

关于红黑树的详细介绍，可参考公众号程序员小灰的文章：

算法题oj地址LintCode：

在线OJ练习地址：二叉树的前序遍历
在线OJ练习地址：二叉树的中序遍历
在线OJ练习地址：二叉树的后序遍历
在线OJ练习地址：二叉树的层次遍历

关于二叉树的面试题：

在秋招的面试过程中，手撕算法算是家常便饭的了。在我面试中，第一次面试的便是字节跳动面试官出的“判断一个树是否是对称二叉树”，紧接着，在百度的面试中，考的是“把一个二叉树转换成它的镜像二叉树”，在小米的面试中，考的是“打印一个二叉树的第K层节点”。

对于解这类问题，我们只有在掌握了二叉树的三种遍历的递归与迭代两种方式的基础之上，才可能在这些问题上游刃有余。

树的遍历：

前序遍历：先访问根节点，然后再一次访问根的左节点和右节点。

前序遍历算法：

在线OJ练习地址：lintcode-前序遍历

递归版代码如下：

public 

非递归版代码如下：

import 

比较：

迭代与递归是编程时的两种常见手法。

在递归程序中，是通过系统栈来保存临时变量。

将递归程序更改为迭代程序，需要自己建立一个栈来保存程序中的临时变量。由于先序遍历，是先访问根节点，然后在访问根节点的同时，将根的左孩子和右孩子放入栈中。访问该节点时，对应的是栈的出栈操作。由于根节点先进后出的特性，所以在这里需要先将右孩子节点入栈，然后再将左孩子节点入栈。这样就能保证先遍历左节点，再遍历右节点。

中序遍历：先遍历左孩子节点，再遍历根节点，最后遍历右孩子节点。

中序遍历算法：

在线OJ练习地址：二叉树的中序遍历

递归版代码

public 

非递归版代码：

public 

分析：

由于中序遍历，是先遍历左节点。所以，在迭代的过程中，将所有的左孩子节点入栈。直到遍历到最左的孩子节点。然后依次出栈。将最底层的右孩子节点入栈。这样便完成了中序遍历。

后序遍历：先遍历左孩子节点，再遍历右孩子节点，最后遍历根节点。

后序遍历算法：

在线OJ练习地址：二叉树的后序遍历

递归版代码

public 

非递归版代码

后续遍历中的非递归代码，是三种遍历方式中，非递归代码最困难的一种。在二叉树的遍历方式中，程序会对二叉树中的每个节点访问两次。

方法一：在前序遍历的基础上修改

前序遍历的访问顺序是根，左，右。而后续遍历的节点访问顺序是左，右，根。若把前序遍历的顺序改为根 ，右，左。最后，将结果倒置一下，即为后序遍历的结果。

代码如下：

public 

方法二：基于栈的方式。通过变量prev，记录前一个访问的节点来实现。

public 

在非递归遍历的后序遍历算法中，通过prev和curr之间的关系，判断是第一次访问还是第二次访问。入栈的逻辑与中序遍历入栈的逻辑类似。都是先将左子树入栈，然后再将右子树入栈。当程序遍历到叶子节点，或者当前节点的右孩子节点已经遍历（即curr.right==prev）时，出栈。

层次遍历：每一层按照从左到右的顺序打印节点

基础层次遍历算法：

通过使用队列来存放下一层节点，实现层次遍历。

public 

按层次遍历算法：

在线OJ练习地址：二叉树的层次遍历

代码

public 

总结：

本文回顾和整理了二叉树的基本遍历算法。包括前序遍历，中序遍历，后续遍历，层次遍历等基础算法。在面试的过程中，关于二叉树的算法，都是基于树的遍历的基础之上来实现的。比如，求二叉树的高度，二叉树的最短路径，和为某一特定值的路径等等。

关于二叉树的相关面试题，会在后续系列讨论。