面试大总结之二：Java搞定面试中的二叉树题目(四)
解法 ，用栈先把根节点的所有左孩子都添加到栈内，
* 然后输出栈顶元素，再处理栈顶元素的右子树
* http://www.youtube.com/watch v=50v1sJkjxoc
*
* 还有一种方法能不用递归和栈，基于线索二叉树的方法，较麻烦以后补上
* http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
*/
public static void inorderTraversal(TreeNode root){
if(root == null){
return;
}
Stack stack = new Stack();
TreeNode cur = root;
while( true ){
while(cur != null){ // 先添加一个非空节点所有的左孩子到栈
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()){
break;
}
// 因为此时已经没有左孩子了，所以输出栈顶元素
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right; // 准备处理右子树
}
}
/**
* 后序遍历递归解法
* （1）如果二叉树为空，空操作
* （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点
*/
public static void postorderTraversalRec(TreeNode root) {
if (root == null) {
return;
}
postorderTraversalRec(root.left);
postorderTraversalRec(root.right);
System.out.print(root.val + " ");
}
/**
* 后序遍历迭代解法
* http://www.youtube.com/watch v=hv-mJUs5mvU
*
*/
public static void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack s = new Stack(); // 第一个stack用于添加node和它的左右孩子
Stack output = new Stack();// 第二个stack用于翻转第一个stack输出
s.push(root);
while( !s.isEmpty() ){ // 确保所有元素都被翻转转移到第二个stack
TreeNode cur = s.pop(); // 把栈顶元素添加到第二个stack
output.push(cur);
if(cur.left != null){ // 把栈顶元素的左孩子和右孩子分别添加入第一个stack
s.push(cur.left);
}
if(cur.right != null){
s.push(cur.right);
}
}
while( !output.isEmpty() ){ // 遍历输出第二个stack，即为后序遍历
System.out.print(output.pop().val + " ");
}
}
/**
* 分层遍历二叉树（按层次从上往下，从左往右）迭代
* 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点
* ，访问，若左子节点或右子节点不为空，将其压入队列
*/
public static void levelTraversal(TreeNode root) {
if (root == null) {
return;
}
LinkedList
queue = new LinkedList();
queue.push(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.removeFirst();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}
/**
* 分层遍历二叉树（递归）
* 很少有人会用递归去做level traversal
* 基本思想是用一个大的ArrayList，里面包含了每一层的ArrayList。
* 大的ArrayList的size和level有关系
*
* 这是我目前见到的最好的递归解法！
* http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal#answer-container-2543
*/
public static void levelTraversalRec(TreeNode root) {
ArrayList> ret = new ArrayList>();
dfs(root, 0, ret);
System.out.println(ret);
}
private static void dfs(TreeNode root, int level, ArrayList> ret){
if(root == null){
return;
}
// 添加一个新的ArrayList表示新的一层
if(level >= ret.size()){
ret.add(new ArrayList());
}
ret.get(level).add(root.val); // 把节点添加到表示那一层的ArrayList里
dfs(root.left, level+1, ret); // 递归处理下一层的左子树和右子树
dfs(root.right, level+1, ret);
}
/**
* 将二叉查找树变为有序的双向链表 要求不能创建新节点，只调整指针。
* 递归解法：
* 参考了http://stackoverflow.com/questions/11511898/converting-a-binary-search-tree-to-doubly-linked-list#answer-11530016
* 感觉是最清晰的递归解法，但要注意递归完，root会在链表的中间位置，因此要手动
* 把root移到链表头或链表尾
*/
public static TreeNode convertBST2DLLRec(TreeNode root) {
root = convertBST2DLLSubRec(root);
// root会在链表的中间位置，因此要手动把root移到链表头
while(root.left != null){
root = root.left;
}
return root;
}
/**
* 递归转换BST为双向链表(DLL)
*/
publi