【数据结构与算法】二叉树的中序遍历

梦里梦外; 2024-04-17 21:23 62阅读 0赞

深度优先遍历：前序-PreOder/中序-InOrder/后序-PostOrder  
广度优先遍历：层次-LevelOrder

**小提示： 搜索二叉树的中序遍历是一个递增序列**

--------------------

二叉树的先序/中序/后序遍历是针对根节点的遍历作为基准点，中序遍历的顺序就是Left Root Right的顺序来  
leetcode-94-Binary Tree Inorder Traversal

##### 方法一 递归 #####

const inorderTraversal = function(node) { 
    	const result = []
    	var helpFunc = (node) => { 
    		if (node) { 
    			if (node.left) {  helpFunc(node.left) }
    			result.push(node.val)
    			if (node.right) {  helpFunc(node.right) }
    		}
    	}
    	helpFunc(node)
    	return result
    }

--------------------

##### 方法二 栈 #####

递归算法可以用栈来实现，栈是先进后出，后进先出。  
中序非递归的关键点：在遍历某个节点的整个左子树后，如何定位到根节点和右子树。

基本思想：

1.  建立一个栈
2.  根节点进栈，遍历左子树。
3.  根节点出栈，输出根节点，遍历右子树。

var inorderTraversal = function (root) {  
      const result = []
      const stack = []
      let node = root
      while(node !== null || stack.length !== 0) { 
    	
    	if (node) { 
    		stack.push(node)
    		node = node.left
    	} else { 
    	 // 左子节点没了
    	 let cur = stack.pop()
    	 result.push(cur.val)
    	 node = cur.right
    	}
      }  
     return result
    }

tip：

1.  深度优先遍历的非递归算法通过Stack-栈来实现【先进后出】
2.  广度优先遍历的非递归算法通过Queue-队列来实现【先进先出】

--------------------

致敬： 非递归算法 来自于 青岛大学 王卓老师的[bilibili课程][bilibili]

[bilibili]: https://www.bilibili.com/video/av35339922