算法中树形迭代的在代码中的两种写法
Updated:
至顶向下
形式如下：
public void f(){
//iterative export
//do something
f();
f();
return;
}
每次迭代会先依据父节点进行一些操作，对以后的迭代会产生一些影响，一般用在不用遍历完所有树空间的情况下
例如1：
判断一棵树是否被另一棵树包含—-无返回值
public boolean isContain = false;
/**
*
* 判断一棵树是否被另一棵树包含
*/
public void search(TreeNode src, TreeNode dst){
//迭代出口
if (src == null){
return;
}
//是否找到结果
if(!isContain ){
isContain = cmpTree(src, dst);
search(src. leftChild, dst);
search(src. rightChild, dst);
}
}
这里的cmpTree函数是用来判定两个树是否相等，如果相等，就停止后面的迭代，如果换成
if (!isContain ){
search(src. leftChild , dst);
search(src. rightChild , dst);
isContain = cmpTree(src, dst);
}
则迭代操作控制起不到作用
例2：
判断两树是否相等—-有返回值
/**
*
* 判断两树是否相等
*/
public boolean cmpTree(TreeNode src, TreeNode dst){
//迭代出口 如果同时达到叶子节点，说明两树相等
if(src == null && dst == null){
return true ;
} else if (src == null || dst == null){
return false ;
}
if (src.data == dst.data){
return cmpTree(src.leftChild ,dst.leftChild) && cmpTree(src.rightChild,dst.rightChild );
} else{
return false ;
}
}
例3：
快速排序—-无返回值
/**
* 划分问题空间
*/
public static void quickSort(int[] data, int start, int end) {
if (start < end) {
int standard = partition(data, start, end);
quickSort(data, start, standard - 1);
quickSort(data, standard + 1, end);
}
}
这里的partition函数对后面的迭代产了影响
至底向上
形式如下：
public void f(){
//iterative export
f();
f();
//do something
return;
}
一般分治法都是使用的至底向上，先把问题空间分成一个一个不能再分的小空间，分别对这些小空间进行求解，父节点的求解依赖于其子节点的求解
例1
归并排序—-无返回值
/**
* 划分问题空间
*/
public static void mergeSort(int[] data, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mergeSort(data, start, middle);
mergeSort(data, middle + 1, end);
merge(data, start, end);
}
}
这里依赖关系不明显，data[]作为参数传入，merge函数的每步求解都依赖于其子节点之前在data数组上的操作
例2
求数组最大值与最小值—-有返回值
public Result search(int start, int end) {
if (start == end) {
Result r = new Result(data [start], data[start]);
return r;
}
int mid = (start + end) / 2;
Result rLeft = search(start, mid);
Result rRight = search(mid + 1, end);
return Result.cmpResult(rLeft, rRight);
}
这里依赖关系就很明显，注意这段语句
if (start == end) {
Result r = new Result(data [start], data[start]);
return r;
}
这里是所有叶子节点至底向上的开始，光靠
Result rLeft = search(start, mid);
Result rRight = search(mid + 1, end);
这两句是不能得到初始数据的
同样，看看例子3
求树中两节点的最大间距—-有返回值
public int maxDistance = 0;
public int getDistance(TreeNode root){
if(root == null){
return 0;
}
int leftDistance = getDistance(root.leftChild );
int rightDistance = getDistance(root.rightChild );
maxDistance = Math.max( maxDistance, leftDistance + rightDistance + 1);
return Math.max(leftDistance + 1, rightDistance + 1);
}