leetcode144：二叉树的前序遍历 #37

Activity

1. sisterAn

   added

   LeetCode

   on May 10, 2020
2. 7777sea commented on May 11, 2020

   

   7777sea

   on May 11, 2020

   More actions

   var preorderTraversal = function(root) {
       let stack = [root]
       let arr = []
       while (stack.length > 0) {
           let node = stack.pop();
           node && arr.push(node.val); // node不为空时，向arr中推入节点值
           node && node.right && stack.push(node.right); // 模拟栈，所以先压右节点
           node && node.left && stack.push(node.left); // 后入先出，后压左节点
       }
       return arr
   };
   

   👍React with 👍1Reacted by SunY
3. plane-hjh commented on May 11, 2020

   

   plane-hjh

   on May 11, 2020

   Last edited by plane-hjh

   More actions

   前序遍历

   先访问根节点，再访问左节点，最后访问右节点。主要是看非递归版本的实现

   递归实现

   // 递归版本
   const preOrderTraverse = (root) => {
       let list = []
   
       const preOrder = (node) => {
           if(node !== null) {
               // 先访问根节点
               list.push(node.val)
               // 再访问左节点
               preOrder(node.left)
               // 最后访问右节点
               preOrder(node.right)
           }
       }
       preOrder(root)
   
       return list
   }

   非递归实现

   // 非递归版本
   const preOrderTraverseUnRecur = (root) => {
       let list = [];
       let stack = [root];
   
       while(stack.length !== 0) {
           const curNode = stack.pop()
   
           const left = curNode.left
           const right = curNode.right
   
           // 第一步的时候，先访问的是根节点
           list.push(curNode.val)
   
           if(right) {
               stack.push(right)
           }
   
           // 因为pop是取出最后一个元素，所以我们要确保首先拿到的是左节点
           if(left) {
               stack.push(left)
           }
       }
   }
4. sisterAn commented on May 11, 2020

   

   sisterAn

   on May 11, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   递归实现

   // 前序遍历
   var preorderTraversal = (root) => {
       let result = []
       var preOrderTraverseNode = (node) => {
           if(node) {
               // 先根节点
               result.push(node.val)
               // 然后遍历左子树
               preOrderTraverseNode(node.left)
               // 再遍历右子树
               preOrderTraverseNode(node.right)
           }
       }
       preOrderTraverseNode(root)
       return result
   };

   迭代实现

   利用栈来记录遍历的过程，实际上，递归就使用了调用栈，所以这里我们可以使用栈来模拟递归的过程

   • 首先根入栈
   • 将根节点出栈，将根节点值放入结果数组中
   • 然后遍历左子树、右子树，因为栈是先入后出，所以，我们先右子树入栈，然后左子树入栈
   • 继续出栈（左子树被出栈）…….

   依次循环出栈遍历入栈，直到栈为空，遍历完成

   // 前序遍历
   const preorderTraversal = (root) => {
       const list = [];
       const stack = [];
       
       // 当根节点不为空的时候，将根节点入栈
       if(root) stack.push(root)
       while(stack.length > 0) {
           const curNode = stack.pop()
           // 第一步的时候，先访问的是根节点
           list.push(curNode.val)
           
           // 我们先打印左子树，然后右子树
           // 所以先加入栈的是右子树，然后左子树
           if(curNode.right !== null) {
               stack.push(curNode.right)
           }
           if(curNode.left !== null) {
               stack.push(curNode.left)
           }
       }
       return list
   }

   复杂度分析：

   空间复杂度：O(n)

   时间复杂度：O(n)

   leetcode
5. sisterAn

   added

   字节

   on May 12, 2020
6. AnranS commented on Nov 19, 2020

   

   AnranS

   on Nov 19, 2020

   More actions

   var preorderTraversal = function (root) {
       if (!root) return [];
       let stack = [root];
       let res = [];
   
       while (stack.length) {
           let node = stack.pop();
           res.push(node.val);
           if (node.right) {
               stack.push(node.right);
           }
           if (node.left) {
               stack.push(node.left);
           }
       }
       return res;
   };
7. kangkang123269 commented on Feb 23, 2023

   

   kangkang123269

   on Feb 23, 2023

   More actions

   非递归版

   function preorderTraversal(root) {
     if (!root) {
       return [];
     }
   
     const stack = [root];
     const result = [];
   
     while (stack.length > 0) {
       const node = stack.pop();
       result.push(node.val);
   
       // 先将右子树入栈，再将左子树入栈，保证先遍历左子树
       if (node.right) {
         stack.push(node.right);
       }
   
       if (node.left) {
         stack.push(node.left);
       }
     }
   
     return result;
   }