leetcode94：二叉树的中序遍历 #38

Activity

1. sisterAn

   added

   LeetCode

   on May 11, 2020
2. xuanweiH commented on May 12, 2020

   

   xuanweiH

   on May 12, 2020

   Last edited by sisterAn

   More actions

   function midOrderTraserval (node) {
       let list = [];
       let stack = [];
       while(stack.length || node) { 
           if(node) {
               stack.push(node);
               node = node.left;
           } else {
               node = stack.pop();
               list.push(node.value);
               //node.right && stack.push(node.right);
               node = node.right; // 如果没有右子树 会再次向栈中取一个结点即双亲结点
           }
       }
       return list;
   }
   midOrderTraserval(tree);

   😄React with 😄1Reacted by 瓶子君
3. 7777sea commented on May 12, 2020

   

   7777sea

   on May 12, 2020

   Last edited by sisterAn

   More actions

   function a (root){
           let arr = []
           let stackArr = []
           while(root!=null || stackArr.length!=0){
   
               while(root!=null){
                   stackArr.push(root)
                   root = root.left
               }
               root = stackArr.pop()
               arr.push(root.val)
               root = root.right
           }
           return arr
   }

   😄React with 😄1Reacted by 瓶子君
4. luweiCN commented on May 12, 2020

   

   luweiCN

   on May 12, 2020

   Last edited by luweiCN

   More actions

   var inorderTraversal = 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.right, current, current.left); // 不管三七二十一，按照右根左的顺序全部入栈，即使有null的也会在上面continue的时候跳过
       } else {
         // 节点已经被访问了，输出值，遍历栈里的下一个节点
         res.push(current.val);
       }
     }
     return res;
   };
5. plane-hjh commented on May 12, 2020

   

   plane-hjh

   on May 12, 2020

   More actions

   中序遍历

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

   递归版本

   // 递归版本
   const inOrderTraverse = (root) => {
       let list = []
   
       const inOrder = (node) => {
           if(node !== null) {
               inOrder(node.left)
               list.push(node.val)
               inOrder(node.right)
           }
       }
   
       inOrder(root)
   
       return list
   }

   迭代版本

   // 非递归版本
   const inOrderTraverseUnRecur = (root) => {
       let list = []
       // 借助了栈，先进后出的概念
       let stack = []
       let head = root
   
       while(stack.length !== 0 || head !== undefined) {
           while(head !== undefined) {
               stack.push(head)
               head = head.left
           }
   
           if(stack.length !== 0) {
               head = stack.pop()
               list.push(head.val)
               head = head.right
           }
       }
   
       return list
   }
6. sisterAn

   added

   字节

   on May 12, 2020
7. sisterAn commented on May 12, 2020

   

   sisterAn

   on May 12, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   递归实现

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

   迭代实现

   const inorderTraversal = function(root) {
       let list = []
       let stack = []
       let node = root
       while(stack.length || node) { 
           if(node) {
               stack.push(node)
               node = node.left
               continue
           }
           node = stack.pop()
           list.push(node.val)
           node = node.right
       }
       return list
   };

   进一步简化：

   // 中序遍历
   const inorderTraversal = (root) => {
       let list = []
       let stack = []
       let node = root
       
       while(node || stack.length) {
       // 遍历左子树
         while(node) {
          stack.push(node)
           node = node.left
         }
         
         node = stack.pop()
         list.push(node.val)
         node = node.right
       }
       return list
   }

   复杂度分析：

   空间复杂度：O(n)
   时间复杂度：O(n)

   leetcode
8. whitesky1225 commented on May 18, 2020

   

   whitesky1225

   on May 18, 2020

   Last edited by whitesky1225

   More actions

   我就来个最简单的递归版本吧。。

   var inorderTraversal = function(root) {
       let list = []
       function inorderTraversalNode(node){
           if(node){
               inorderTraversalNode(node.left)
               list.push(node.val)
               inorderTraversalNode(node.right)
           }
       }
       inorderTraversalNode(root)
       return list 
   };