144_145_94_二叉树遍历.md

题目

前中后序遍历, 相关题目

• https://leetcode.cn/problems/binary-tree-inorder-traversal/
• https://leetcode.cn/problems/binary-tree-preorder-traversal/
• https://leetcode.cn/problems/binary-tree-postorder-traversal/

注意: 请使用多种方式实现二叉树的遍历

前序遍历

递归的代码是很简单的

void dfs(Node n){
	if(n==null) return ;
	res.add(n.val);
	dfs(n.left);
	dfs(n.right);
}

但是方法栈如果递归过深, 可能会导致栈溢出 , 并且递归写法很难有区分度

因此迭代写法是十分必要的, 关键点在于 : 通过 栈对象来模拟方法栈的 形式

对于前序遍历 , 我们思考递归的代码,

1. 首先添加val , 然后遍历左节点
2. 与此同时 , 我们需要暂存当前节点 , 毕竟后续还要继续遍历(当前节点的右子树)
3. 当根节点遍历完(node==null) , 回溯到上次一的 dfs , 调用右节点 (由于2, 右节点我们已经缓存到栈中)
4. 对于节点 当成 子树 , 那么就是遍历右子树

 // 伪代码
var st;
var res;
var cur=root;
while(cur!=null || st.size()!=0){
    while(cur!=null){
        res.add(cur.val); // 参考1
        st.push(cur);// 参考2
        cur=cur.left;
    }
   	cur = st.pop().right;
}

return res;

中序遍历

void dfs(Node n){
	if(n==null) return ;
	dfs(n.left);
	res.add(n.val);
	dfs(n.right);
}

1. 先到left的叶子
2. 遍历到左叶子, 开始添加值
3. 遍历完当前的值, 开始遍历右子树

 // 伪代码
var st;
var res;
var cur=root;
while(cur!=null || st.size()!=0){
    while(cur!=null){
        st.push(cur);// 1
        cur=cur.left;
    }
    var node = st.pop();
    res.add(node.val);// 2
    cur = node.right; // 3
}

return res;

后续遍历

左右根难以实现

我们通过 根右左 然后配置反转即可

根右左

void dfs(Node n){
	if(n==null) return ;
	res.add(n.val);
	dfs(n.right);
	dfs(n.left);
}

对应的迭代

1. 每次遍历添加当前的节点值 , 然后访问右节点 (根-> 右)
2. 访问完右子树, 访问左子树

 // 伪代码
var st;
var res;
var cur=root;
while(cur!=null || st.size()!=0){
    while(cur!=null){
    	res.add(cur.val);// 1
        st.push(cur);// 1
        cur=cur.right;
    }
    var node = st.pop();
    cur = node.left; // 3
}
Collections.reverse(res);

return res;

关于每次通过 栈来进行st.push(cur) 可以理解为保存当前 节点的 "上下文"