leetcode145：二叉树的后序遍历 #40

Activity

1. sisterAn

   added

   LeetCode

   字节

   on May 12, 2020
2. 7777sea commented on May 13, 2020

   

   7777sea

   on May 13, 2020

   Last edited by sisterAn

   More actions

   var postorderTraversal = function(root) {
       let res = []  // 用来存储后序遍历节点的值
           stack = []  
           cur = root
   
       var lastVisitedNode = null;
       while(cur || stack.length > 0) {
           if(cur !== null){
               stack.push(cur);
               cur = cur.left;
           } else {
               cur = stack.pop();
               if(cur.right === null || lastVisitedNode === cur.right) {
                   res.push(cur.val);
                   lastVisitedNode = cur;
                   cur = null;
               } else {
                   stack.push(cur);
                   cur = cur.right;
               }
           }
       }
       return res;
   };
3. plane-hjh commented on May 13, 2020

   

   plane-hjh

   on May 13, 2020

   More actions

   后序遍历

   • 后序遍历：先访问左节点，再访问右节点，最后访问根节点

   递归版本

   // 递归
   const postOrderTraverse = (root) => {
       let list = []
   
       const postOrder = (node) => {
           if(!node) {
               postOrder(node.left)
               postOrder(node.right)
               list.push(node.val)
           }
       }
   
       postOrder(root)
   
       return list
   }

   迭代版本

   // 非递归
   const postOrderTraverseUnRecur = (root) => {
       let list = []
       if(root !== undefined) {
           let s1 = []
           let s2 = []
   
           s1.push(root)
   
           while(s1.length !== 0) {
               head = s1.pop()
               s2.push(head)
   
               if(head.left !== undefined) {
                   s1.push(head.left)
               }
   
               if(head.right !== undefined) {
                   s1.push(head.right)
               }
           }
   
           while(s2.length !== 0) {
               var item = s2.pop()
               list.push(item.val)
           }
       }
   
       return list
   }
4. luweiCN commented on May 13, 2020

   

   luweiCN

   on May 13, 2020

   More actions

   var postorderTraversal = function (root) {
     if (root === null) return [];
     let stack = [root];
     let res = [];
     while (stack.length) {
       let current = stack.pop();
       if (current === null) continue;
       if (!current.visited) {
         current.visited = true;
         stack.push(current, current.right, current.left);
       } else {
         res.push(current.val);
       }
     }
   
     return res;
   };
5. syc666 commented on May 13, 2020

   

   syc666

   on May 13, 2020

   Last edited by syc666

   More actions

   const fun = (tree) => {
       //迭代
       let res = []
       const stack = []
       if(tree) stack.push(tree)
       while(stack.length>0){
           const chTree = stack.pop()
           if(chTree.left) stack.push(chTree.left)
           if(chTree.right) stack.push(chTree.right)
           res.unshift(chTree.val)
       }
       return res
   }
6. sisterAn commented on May 13, 2020

   

   sisterAn

   on May 13, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   递归实现

   // 后序遍历
   const postorderTraversal = function(root) {
       let result = []
       var postorderTraversalNode = (node) => {
           if(node) {
               // 先遍历左子树
               postorderTraversalNode(node.left)
               // 再遍历右子树
               postorderTraversalNode(node.right)
               // 最后根节点
               result.push(node.val)
           }
       }
       postorderTraversalNode(root)
       return result
   };

   迭代实现

   解题思路： 后序遍历与前序遍历不同的是：

   • 后序遍历是左右根

   • 而前序遍历是根左右

   如果我们把前序遍历的 list.push(node.val) 变更为 list.unshift(node.val) （遍历结果逆序），那么遍历顺序就由 根左右 变更为 右左根

   然后我们仅需将 右左根 变更为 左右根 即可完成后序遍

   // 后序遍历
   const postorderTraversal = (root) => {
       const list = [];
       const stack = [];
       
       // 当根节点不为空的时候，将根节点入栈
       if(root) stack.push(root)
       while(stack.length > 0) {
           const node = stack.pop()
           // 根左右=>右左根
           list.unshift(node.val)
           
           // 先进栈左子树后右子树
           // 出栈的顺序就变更为先右后左
           // 右先头插法入list
           // 左再头插法入list
           // 实现右左根=>左右根
           if(node.left !== null) {
               stack.push(node.left)
           }
           if(node.right !== null) {
               stack.push(node.right)
           }
       }
       return list
   }

   复杂度分析：

   空间复杂度：O(n)

   时间复杂度：O(n)

   leetcode

   👍React with 👍10Reacted by xuanweiH, fan, 引川, 白霁, Yifei Cai, crazcdll, kylecui2016, H-Stephen, Drake and 彩虹Rainbow
7. 2hangJing commented on Aug 31, 2021

   

   2hangJing

   on Aug 31, 2021

   Last edited by 2hangJing

   More actions

   后序遍历：l -> r -> m，通过左右镜像得到：m -> r -> l。所以只用实现 根 -> 右 -> 左，再通过 unshift 倒叙输出到数组中即实现后续遍历。

   let postorderTraversal_iteration = (tree)=>{
       let list = [];
       // 根结点入栈
       let stack = [tree];
       while(stack.length>0){
           // 栈顶元素出栈
           let node = stack.pop();
           if(node === null) continue;
           // 通过倒叙输出将 根->右->左 转换成 左->右->根（后续遍历）
           list.unshift(node.val);
           stack.push(node.left);
           stack.push(node.right);
       }  
       return list;
   }