遍历二叉树的统一迭代法

二叉树的统一迭代法

普通迭代遍历方式无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况,前中后序的迭代法各有区别，那么如何实现统一的代码写法呢

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢? 

就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

JavaScript代码:

迭代法中序遍历

/**
  * @param {TreeNode} root
  * @return {number[]}
  */
 var inorderTraversal = function(root) {
   // 统一迭代法
   const res = []
   if(!root) return res
   const stack = [root]
   while(stack.length){
     const n = stack.pop()
     if(!n){ // 只有遇到空节点的时候，才将下一个节点放进结果集
       res.push(stack.pop().val)
       continue
     }
 ​
     n.right && stack.push(n.right)  // 右先放入栈后访问
     stack.push(n)
     stack.push(null)  // 节点访问过，但是还没有处理，加入空节点做为标记。
     n.left && stack.push(n.left)  //左后放入栈先访问   实现 左-中-右
   }
   return res
 }

迭代法先序遍历

 /**
  * @param {TreeNode} root
  * @return {number[]}
  */
 var inorderTraversal = function(root) {
   // 统一迭代法
   const res = []
   if(!root) return res
   const stack = [root]
   while(stack.length){
     const n = stack.pop()
     if(!n){ // 只有遇到空节点的时候，才将下一个节点放进结果集
       res.push(stack.pop().val)
       continue
     }
 ​
     stack.push(n)
     stack.push(null)  // 节点访问过，但是还没有处理，加入空节点做为标记。
     n.right && stack.push(n.right)  // 右先放入栈后访问
     n.left && stack.push(n.left)  // 左后放入栈先访问   实现 中-左-右
     
   }
   return res
 }

迭代法后序遍历

/**
  * @param {TreeNode} root
  * @return {number[]}
  */
 var inorderTraversal = function(root) {
   // 统一迭代法
   const res = []
   if(!root) return res
   const stack = [root]
   while(stack.length){
     const n = stack.pop()
     if(!n){ // 只有遇到空节点的时候，才将下一个节点放进结果集
       res.push(stack.pop().val)
       continue
     }
 ​    stack.push(n)
     stack.push(null)  // 节点访问过，但是还没有处理，加入空节点做为标记。
     n.left && stack.push(n.left)  //左先放入栈后访问   
     n.right && stack.push(n.right)  // 右后放入栈先访问  实现 左-右-中
   }
   return res.reverse() // 结果集倒序输出即可
 }

 可以做一做leetcode上三道题目，分别是：

• 144.二叉树的前序遍历(opens new window)https://leetcode.cn/problems/binary-tree-preorder-traversal/
• 145.二叉树的后序遍历(opens new window)https://leetcode.cn/problems/binary-tree-postorder-traversal/
• 94.二叉树的中序遍历https://leetcode.cn/problems/binary-tree-inorder-traversal/