本文共 2900 字,大约阅读时间需要 9 分钟。
把原本的递归形式转换成迭代的形式,但是整体的思想还是不变的,
其实就是把递归的过程 翻译 成while + if 。Morris Traversal 线索树
时间是O(n) 空间O(1)的解法 : 参考: https://blog.csdn.net/dxx707099957/article/details/88550437?utm_medium=distribute.pc_relevant.none-task-blog-title-2&spm=1001.2101.3001.4242要使用O(1)空间进行遍历,最大的难点在于,遍历到子节点的时候怎样重新返回到父节点(假设节点中没有指向父节点的p指针),由于不能用栈作为辅助空间。为了解决这个问题,Morris方法用到了线索二叉树(threaded binary tree)的概念。在Morris方法中不需要为每个节点额外分配指针指向其前驱(predecessor)和后继节点(successor),只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了。
public ListinorderTraversal(TreeNode root) { List ans= new ArrayList<>(); TreeNode cur = root, pre = null; while (cur != null) { if (cur.left == null) { ans.add(cur.val); cur = cur.right;// 前进,可能到真正的右儿子,也可能是下一个节点 } else { pre = cur.left; while (pre.right != null && pre.right != cur) pre = pre.right; if (pre.right == null) { //右儿子是空 pre.right = cur; cur = cur.left; // 并不是前进,相当于递归找cur.left的前驱 } else { // 右儿子是cur,说明指针已经被置为下一个节点了 ans.add(cur.val); pre.right = null; cur = cur.right;//前进,一定是下一个节点 } } } return ans; }
public ListinorderTraversal(TreeNode root) { List ans = new ArrayList<>(); Stack stk = new Stack<>(); TreeNode leftNode = root; while (leftNode != null) { //先特殊处理root的左链 stk.push(leftNode); leftNode = leftNode.left; } while (!stk.empty()) { TreeNode tmp = stk.pop(); ans.add(tmp.val); tmp = tmp.right; while (tmp != null) { stk.push(tmp); tmp = tmp.left; } } return ans; }
public ListpreorderTraversal(TreeNode root) { LinkedList ans = new LinkedList<>(); if (root == null) return ans; Stack stk = new Stack<>(); stk.push(root); while (!stk.empty()) { TreeNode p = stk.pop(); ans.add(p.val); if (p.right != null) stk.push(p.right); if (p.left != null) stk.push(p.left); } return ans; }
public ListpostorderTraversal(TreeNode root) { LinkedList ans = new LinkedList<>(); if (root == null) return ans; Stack stk = new Stack<>(); stk.push(root); while (!stk.empty()) { TreeNode tmp = stk.pop(); ans.addFirst(tmp.val); if (tmp.left != null) stk.push(tmp.left); if (tmp.right != null) stk.push(tmp.right); } return ans; }