leetcode94：二叉树的中序遍历

[sisterAn]

给定一个二叉树，返回它的 中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶:  递归算法很简单，你可以通过迭代算法完成吗？

附赠leetcode地址：leetcode

[xuanweiH]

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);

[7777sea]

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
}

[luweiCN]

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;
};

[plane-hjh]

中序遍历

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

递归版本

// 递归版本
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
}

[sisterAn]

递归实现

// 中序遍历
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

[whitesky1225]

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

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 
};