牛客算法--第七章

牛客算法–第七章

题目一
分别用递归和非递归方式实现二叉树先序、中序和后序遍历
【题目】
用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。

前序遍历为“根左右”：

递归C++版本：

void preorder(node* root) 
{
	if(root==NULL)
	{
		return;	//到达空树，递归边界 
	}
	
	//访问根结点root,例如将其数据域输出 
	printf("%d\n",root->value);
	
	//访问左子树
	preorder(root->lchild);
	
	//访问右子树
	preorder(root->rchild); 
	 
	
	
}

非递归JAVA版本：

public static void preOrderUnRecur(Node head){
	
	System.out.print("preorder: ");
	
	if(head != null)
	{
		Stack<Node> stack = new Stack<Node>();
		stack.add(head);
		
		while(!stack.isEmpty()){
			
			head = stack.pop();
			Systemp.out.print(head.value + " ");
			
			if(head.right != null)
			{
				stack.push(head.right);
				
			}
			
			if(head.left != null)
			{
				stack.push(head.left)
				
			}
			
			
		}
		
		
		
		
	}
	
	
	System.out.println();
	
	
}

非递归版本核心思想就是用栈。
因为先序遍历的要求是“根左右”，而栈的结构是完成数据先进后出的。所以我们应该先判断一个结点右子树是否为空，如果不为空，就将其压入栈中；然后再判断一个结点左子树是否为空，如果不为空，就将其压入栈中。这样就保证了一个结点的左子树先于右子树弹出栈。我们遍历的过程就是弹出栈的过程，我们总是弹出栈顶最高的结点，如果该结点有左右子结点，就将其子结点按“先右后左”的顺序压入栈中；如果没有的话，也就是叶子结点，因为有if语句的判断作用，它没有子结点会在这一回合压入，并且会将其自身从栈中弹出。

中序遍历为“左根右”：

递归C++版本：

void inorder(node* root)
{
	
	if(root == NULL)
	{
		return;
	}
	
	inorder(root->lchild);
	
	printf("%d\n",root->value);
	
	inorder(root->rchild);
	
	
	
	
}

非递归JAVA版本：

public static void inOrderUnRecur(Node head){
	
	System.out.print("inorder: ");
	
	if(head != null)
	{
		
		Stack<Node> stack = new Stack<Node>();
		
		while(!stack.isEmpty() || head != null ){
			
			if(head != null){
				
				stack.push(head);
				head = head.left;
				
			}else{
				
				head = stack.pop();
				System.out.print(head.value + " " );
				head = head.right;
				
				
			}
			

		}

	}
	
	System.out.println();
	
}

非递归中序遍历的顺序因为是“左根右”，我们实际上把一颗树想成下面：

    /
   /    /
  /    / /
 / /    /

就是想成一排排左斜线的样子。
就是有一丝丝“左倾”的分子都要让他入栈。啥意思呢？就是第一优先级是“左左”，第二优先级是“右左”。

后序遍历为“左右根”：

递归C++版本：

void postorder(node* root)
{
	if(root == NULL)
	{
		return;
		
	} 
	
	postorder(root->lchild);
	postorder(root->rchild);
	
	printf("%d\n",root->value);
	
	
}

非递归JAVA版本：

非递归后序遍历的核心思想是用两个栈stack1和stack2.后序遍历要求的是“左右根”，我们看一下它的逆序，就是“根右左”，那么，如何做呢？就是前面非递归先序遍历中，栈中先压右后压左，最终实现了“根左右”，现在我们栈中先压左后压右，自然就可以得到“根右左”了。接下来第二个stack2的作用实际上就是起一个逆序的作用，最终就可以得到“左右根”的效果了。当然，实现逆序，也不一定用栈，我们可以存储在容器中，然后进行reverse就可以了。

提前预告，下面的题目二和题目三都是套路题，要掌握。

题目二
找到二叉树中的最大搜索二叉子树
【题目】
给定一棵二叉树的头节点 head，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子
树，并返回这棵子树的头节点。
【要求】
如果节点数为 N，要求时间复杂度为 O(N)，额外空间复杂度为 O(h)，h 为二叉树的高度。

首先，要弄明白最大子树和最大拓扑结构的**区别。**一个点包括左右子树都满足条件，这个点为根结点的树才算是一颗符合条件的子树。

假如我们有一个函数F(…)可以返回以下4个信息：

1.最大搜索子树头结点
2.整棵树的min值
3.整棵树的max值
4.整棵树符合条件的size

public static Node biggestSubBST(Node head){
	
	//0->size,1->min,2->max
	int[] record = new int[3];
	
	return posOrder(head,record);

	
}

public static Node posOrder(Node head,int[] record){
	
	if(head == null)
	{
		record[0] = 0;
		record[1] = Integer.MAX_VALUE;
		record[2] = Integer.MIN_VALUE;
		return null;	
		
	}
	
	int value = head.value;
	Node left = head.left;
	Node right = head.right;
	Node lBST = postOrder(left,record);
	int lSize = record[0];
	int lMin = record[1];
	int lMax = record[2];
	
	Node rBST = posOrder(right,record);
	int rSize = record[0];
	int rMin = record[1];
	int rMax = record[2];
	
	record[1] = Math.min(lMin,value);
	record[2] = Math.max(rMax,value);
	
	
	if( left == lBST && right == rBST 
		&& lMax < value && value < rMin )
	{
		record[0] = lSize + rSize +1;
		return head;
		
	}
	
	record[0] = Math.max(lSize,rSize);
	
	return lSize > rSize ? lBST : rBST;
	
	
	
}

题目三
二叉树节点间的最大距离问题
【题目】
从二叉树的节点 A 出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点 B 时，路
径上的节点数叫作 A 到 B 的距离。求整棵树上节点间的最大距离。
【要求】
如果二叉树的节点数为 N，时间复杂度要求为 O(N)。

public static int maxDistance(Node head)}{
	
	int[] record = new int[1];
	return posOrder(head,record);

}


public static int posOrder(Node head,int[] record){
	
	if(head == null){
		
		record[0] =0;
		return 0;
		
	}
	
	int lMax = posOrder(head.left,record);
	int maxFromLeft = record[0];
	
	int rMax = posOrder(head.right,record);
	int maxFromRight = record[0];
	
	int curNodeMax = maxFromLeft + maxFromRight+1;
	
	record[0] = Math.max(maxFromLeft, maxFromRight )+1;
	
	return Math.max(Math.max(lMax,rMax),curNodeMax);
	
	
	
	
}

题目五
在二叉树中找到累加和为指定值的最长路径长度
【题目】
给定一棵二叉树的头节点 head 和一个 32 位整数 sum，二叉树节点值类型为整型，求累加和为 sum
的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。
，额外空间复杂度为 O(h)，h 为二叉树的高度。

总结，解决本题需要先复习以下原来的一个算法原型，求一个数组中指定和为k的最长子数组。

怎么求解呢？用到哈希map。

首先在map中插入（0，-1）键值对，因为数组下标是从0开始的，所以提前设置从-1位置开始的值是0。
遍历一遍数组，在遍历的过程中进行累加，累加值是key，如果这个key值在map中没有出现过，就将其加入map中，对应的value值是遍历到的下标，如果已经出现过了，就不进行理会。

算法的原理就是假设从0到i的累加和为num1，我们要求以i结尾的累加和为指定k的最长子数组和，就是从map中找到num1-k对应的key值，找出对应的index，符合条件的最长子数组就是index~i的数组。我们如何求长度呢？i-index+1。
同样我们在遍历的过程中可以得出所有以0~n结尾的累加和为指定k的最长子数组和，所以我们在其中选出一个最大值就可以了。

回归本题，树的操作，和之前的又有一些不同，需要注意数据的保存，在递归的过程中自然实现保存。

代码中的sum就是指定和k，数组中的index，就是对应树中的level：

public static int getMaxLength(Node head,int sum){
	
	HashMap<Integer,Integer> sumMap = new HashMap<Integer,Integer>();
	sumMap.put(0,0);//important
	return preOrder(head,sum,0,1,0,sumMap);
	
	
}


public static int preOrder(Node head,int sum,int preSum,
				int level ,int maxLen,HashMap<Integer,Integer> sumMap  ){
	
	if(head == null)
	{
		return maxLen;
		
	}
	
	int curSum = preSum + head.value;
	
	if(!sumMap.containsKey(curSum)){
		
		sumMap.put(curSum,level);
	}
	
	if(sumMap.containsKey(curSum - sum)){
		
		maxLen = Math.max(level - sumMap.get(curSum - k),maxLen);
		
	}
	
	maxLen = preOrder(head.left,sum,curSum,level+1,maxLen,sumMap);
	
	maxLen = preOrder(head.right,sum,curSum,level+1,maxLen,sumMap);
	
	
	if(level == sumMap.get(curSum)){
		
		sumMap.remove(curSum);
	}
	
	return maxLen;
	
	
}