题目: 二叉树前序遍历非递归实现
总体思路:用非递归的方式模拟递归遍历。
以下图为例:
图示详解:
代码实现:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || stack.isEmpty() == false){//这个循环条件很难想到
while(cur != null){
stack.push(cur);
list.add(cur.val);
cur = cur.left;
}
//此时节点为空
TreeNode top = stack.pop();
cur = top.right;
}
return list;
}
}
题目: 二叉树中序遍历非递归实现
思路:中序非递归遍历和前序非递归遍历总体思路相同,唯一一个区别点是如果cur节点非空时,只压栈,list中并不立即记录当前cur的val值,同时令cur = cur.left。当cur == null时,栈顶元素出栈,此时在list中记录。如下以一组图示进行形象说明。
中序遍历和前序遍历代码处的不同只有一处,如下:
中序遍历非递归完整代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur != null || stack.isEmpty() == false){//这个循环条件很难想到
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
list.add(top.val);
cur = top.right;
}
return list;
}
}
总结:前序、中序非递归遍历,两者只是在节点的记录时机不同,而节点的遍历路径完全相同。这也从根本上导致了两道题的AC代码几乎相同。