树模型在数据结构中应用非常广泛
今天刚好做到leetcode94二叉树的中序遍历，整理一下递归与迭代的解法
吐槽一下力扣的测试用例给的也太不易懂了
中序遍历是先左节点，在中节点（根节点），再右节点
以上述中，前中后序遍历顺序如下：
前序遍历（中左右）：5 4 1 2 6 7 8
中序遍历（左中右）：1 4 2 5 7 6 8
后序遍历（左右中）：1 2 4 7 8 6 5
递归法
递归法按照三要素来写：
1.确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3.确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以下以中序遍历为例子
1.确定递归函数的参数与返回值
要传入当前的节点值node与一个保存结果的列表list，不需要返回值，因此递归的返回类型就是void，代码如下：
public void helper(TreeNode node,List<Integer> list)
2.确定终止条件
在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
if(node==null){
return //如归节点为空，直接返回
}
3.确定单层递归的逻辑：
中序遍历是左中右的循序，所以在单层递归的逻辑，是要先取左节点的数值，若左节点为null,把该节点放入结果集中，再去递归右节点
public void helper(TreeNode node,Listlist){
if(node==null){//如归节点为空，直接返回
return;
}
helper(node.left,list);//首先递归左边直到该节点左节点为null
list.add(node.val);//左节点为null时，该节点加到结果集里
helper(node.right,list);//再递归右边
}
这样二叉树的前序遍历，基本就写完了，在看一下完整代码：
class Solution1 {
public ListinorderTraversal(TreeNode2 root) {
ArrayList result =new ArrayList<>();
helper(root,result);//把节点放进去，包含他的左右，result作为结果集
return result;//最后把结果集返回
}
public void helper(TreeNode2 node,List list){
if(node==null){//如归节点为空，直接返回
return;
}
helper(node.left,list);//首先递归左边直到该节点左节点为null
list.add(node.val);//左节点为null时，该节点加到结果集里
helper(node.right,list);//再递归右边
}
}
迭代法：
迭代法采用栈先进后出的特性，
如果当前节点不为null或者栈内元素大于0，进入循环
若当前节点不为null,栈内加入当前节点，再向下遍历左节点
若当前节点位null，即左子树遍历完成，当前节点转为栈顶元素弹出并加到结果集当中，当前节点转为右子树
public List<Integer> inorderTraversal(TreeNode2 root) {
ArrayList<Integer> result = new ArrayList<>();
Stack<TreeNode2> stack = new Stack<>();
TreeNode2 cur=root;
while (cur!=null||stack.size()>0){
if(cur!=null){
stack.add(cur);
cur=cur.left;
}else {
cur=stack.pop();
result.add(cur.val);
cur=cur.right;
}
}
return result;
}
以上代码可以在IDEA中创建一个树作为测试和debuge
public class TestTree {
public static void main(String[] args) {
//创建二叉树节点
TreeNode2 head =new TreeNode2(1);
TreeNode2 n1 =new TreeNode2(2);
TreeNode2 n2 =new TreeNode2(3);
TreeNode2 n3 =new TreeNode2(4);
TreeNode2 n4 =new TreeNode2(5);
TreeNode2 n5 =new TreeNode2(6);
TreeNode2 n6 =new TreeNode2(7);
//生成二叉树
head.left = n1;
head.right = n2;
n1.left = n3;
n1.right = n4;
n2.left = n5;
n2.right = n6;
//递归方式中序遍历二叉树
Solution3 solution3 =new Solution3();
List result = solution3.inorderTraversal(head);
System.out.println(result);
}
}
class Solution3 {
public ListinorderTraversal(TreeNode2 root) {
ArrayList result =new ArrayList<>();
helper(root,result);//把节点放进去，包含他的左右，result作为结果集
return result;//最后把结果集返回
}
public void helper(TreeNode2 node,List list){
if(node==null){//如归节点为空，直接返回
return;
}
helper(node.left,list);//首先递归左边直到该节点左节点为null
list.add(node.val);//左节点为null时，该节点加到结果集里
helper(node.right,list);//再递归右边
}
}
网友评论