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