递归遍历
前序遍历:根左右
一路俯冲,然后回头
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let result = []
let preOrder = function(node){
if(node==null){
return
}
result.push(node.val)
preOrder(node.left)
preOrder(node.right)
}
preOrder(root)
return result
};
中序遍历:左根右
每个结点的垂直投影
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
let result = []
inOrder(root,result)
return result
};
function inOrder(node,result){
if(node==null){
return
}
inOrder(node.left,result)
result.push(node.val)
inOrder(node.right,result)
}
后序遍历:左右根
剪葡萄,只有剪了子结点才能剪父节点
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let res = []
postOrder(root,res)
return res
};
function postOrder(node,res){
if(node == null){
return
}
postOrder(node.left,res)
postOrder(node.right,res)
res.push(node.val)
}
迭代遍历
前序遍历:
可以用栈模拟一遍:
访问本结点,把右结点压入栈中,访问左结点,若空则弹栈
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
//访问本结点,把右结点压入栈中,访问左结点,若空则弹栈
var preorderTraversal = function(root) {
let result = []
let stack = []
stack.push(root)
let node
//真模拟起来,思路一下就乱了:循环终止条件是什么?循环下一个数是什么
//终止条件应当是栈中无值了;下一个数是弹出的栈顶;
//而且应当有二层循环:终止条件是结点为null,下一个值是node.left
while(stack.length!=0){
node = stack.pop()
while(node!=null){
result.push(node.val)
stack.push(node.right)
node = node.left
}
}
return result
};
另外在看完题解后,发现一个更"精确"的模拟是,把本结点压入栈中,弹出后node=node.right;
此处特地标出,因为和后续的中序更统一
//访问本结点,把本结点压入栈中,访问左结点,若空则弹栈
var preorderTraversal = function(root) {
let result = []
let stack = []
//stack.push(root)
let node = root
while(stack.length!=0||node!=null){
while(node!=null){
result.push(node.val)
stack.push(node)
node = node.left
}
node = stack.pop()
node = node.right
}
return result
};
在看了文章后,我才明白,原来我的方法的和卡哥的方法是不一样的,我的前序中序都是用了指针辅助的,并不是纯用栈;
另外单层循环确实更简洁;
这里标出卡哥的方法
var preorderTraversal = function(root) {
if(root == null){
return []
}
let result = []
let stack = []
stack.push(root)
while(stack.length!=0){
let node = stack.pop()
result.push(node.val)
//注意先压右边后压左边
if(node.right!=null){
stack.push(node.right)
}
if(node.left!=null){
stack.push(node.left)
}
}
return result
};
中序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
//思路:遍历顺序和前序不同;先压栈,node=node.left;然后弹栈时访问本节点;然后node=node.right
var inorderTraversal = function(root) {
let stack = []
let result = []
let node = root
while(stack.length!=0||node!=null){
while(node!=null){
stack.push(node)
node = node.left
}
node = stack.pop()
result.push(node.val)
node = node.right
}
return result
};
如果用卡哥的前序的方法,同样可以用栈,但区分栈中的根节点和右结点有困难
(弹出后不知应当访问左还是访问本右)
所以不能把前序代码改了就用
后序遍历
先还是走一波指针+栈+二重循环的结合;用的是反过来的先序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
//可以按根右左的顺序访问,然后反过来
var postorderTraversal = function(root) {
let res = []
let stack = []
let node = root
while(node!=null||stack.length!=0){
while(node!=null){
stack.push(node)
res.push(node.val)
node = node.right
}
node = stack.pop()
node = node.left
}
return res.reverse()
};
然后是题解中更"精确"的模拟
用一个prev表示上一个被遍历过的(取了值)的右结点
先和中序遍历一样,先压栈到左边;弹出后,判断其right是否等于prev,否则再压栈,node = node.right再进入循环
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let res = []
let stack = []
let node = root
let prev = null
while(stack.length!=0||node!=null){
while(node!=null){
stack.push(node)
node = node.left
}
node = stack.pop()
if(node.right==null||node.right==prev){
res.push(node.val)
prev = node
node = null
}else{
stack.push(node)
node = node.right
}
}
return res
};
还有卡哥的栈的方法(其实也是前序反过来):
/**
* @param {TreeNode} root
* @return {number[]}
*/
//可以按根右左的顺序访问,然后反过来
var postorderTraversal = function(root) {
if(root == null){
return []
}
let res = []
let stack = []
stack.push(root)
while(stack.length!=0){
let node = stack.pop()
res.push(node.val)
if(node.left!=null){
stack.push(node.left)
}
if(node.right!=null){
stack.push(node.right)
}
}
return res.reverse()
};
统一迭代遍历
中序遍历
一切都要从中序遍历讲起...
大致思路是:stack弹栈,然后根据其是否访问过(是"根"还是"右")来决定
访问过了,就取值走人;未访问过,就标记访问,然后按右根左的顺序压栈;
注意:卡哥原文中的标记方法是压入一个NULL,NULL下的就是访问过的;
js更为灵活,所以可以直接取属性;
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
if(root == null){
return []
}
let stack = []
let result = []
stack.push(root)
while(stack.length!=0){
let node = stack.pop()
if(node.visited === undefined){
node.visited = true
if(node.right!=null){
stack.push(node.right)
}
stack.push(node)
if(node.left!=null){
stack.push(node.left)
}
}else{
result.push(node.val)
}
}
return result
};
前序遍历
压栈顺序变成右左根
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
//访问本结点,把本结点压入栈中,访问左结点,若空则弹栈
var preorderTraversal = function(root) {
if(root == null){
return []
}
let result = []
let stack = []
stack.push(root)
while(stack.length!=0){
let node = stack.pop()
if(node.visited){
result.push(node.val)
}else{
node.visited = true
if(node.right!=null){
stack.push(node.right)
}
if(node.left!=null){
stack.push(node.left)
}
stack.push(node)
}
//注意先压右边后压左边
}
return result
};
后序遍历
压栈顺序变成根右左
stack 和res老是搞反,老天爷,有时候我感觉我真的在凭直觉写代码...
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
//可以按根右左的顺序访问,然后反过来
var postorderTraversal = function(root) {
if(root == null){
return []
}
let res = []
let stack = []
stack.push(root)
while(stack.length!=0){
let node = stack.pop()
if(node.visited){
res.push(node.val)
}else{
node.visited = true
stack.push(node)
if(node.right!=null){
stack.push(node.right)
}
if(node.left!=null){
stack.push(node.left)
}
}
}
return res
};
//stack 和res老是搞反,老天爷,有时候我感觉我真的在凭直觉写代码