总结了二叉树的先序、中序、后序遍历算法,分别给出了这三种算法的递归写法和迭代写法。
默认数据结构如下:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
先序
中左右
/**
* Recursive 递归
* 纯函数
*/
var preorderTraversal = function(root) {
var r = [];
if(!root) return [];
r.push(root.val);
if(root.left)
r = r.concat(preorderTraversal(root.left));
if(root.right)
r = r.concat(preorderTraversal(root.right));
return r;
};
/**
* iteratively 迭代
* 思路:首先把根节点入栈,然后迭代以下过程:
* 出栈,输出这个节点,这个节点的右、左子节点依次入栈
*/
var preorderTraversal = function(root) {
const stack = [];
stack.push(root);
const traversal = [];
while (stack.length){
const node = stack.pop();
if (!node){
continue;
}
traversal.push(node.val);
stack.push(node.right);
stack.push(node.left);
}
return traversal;
};
中序
左中右
/**
* Recursive 递归
*/
var inorderTraversal = function(root) {
var r = [];
if(!root) return [];
if(root.left)
r = r.concat(inorderTraversal(root.left));
r.push(root.val);
if(root.right)
r = r.concat(inorderTraversal(root.right));
return r;
};
/*
* iteratively 迭代
*/
var inorderTraversal = function(root) {
let result = [];
let stack = [];
let node = root;
while(stack.length > 0 || node !== null) {
while(node) {
stack.push(node);
node = node.left;
}
if (stack.length !== 0) {
node = Stack.pop();
result.push(node.val);
node = node.right;
}
}
return result;
};
/**
* iteratively 迭代
* 思路:首先把根节点入栈,然后迭代以下过程:
* 1.出栈
* 2.如果这个节点的子节点没有被Push进栈过(判断方法不写了),依次push右子节点、这个节点、左子节点。
* 3.判断是否pop并输出。判断方法:leftChild == null || letfChild == 上一次输出的节点 || 上一次输出的节点的rightChild == null
*/
var inorderTraversal = function(root) {
const stack = [];
const traversal = [];
let lastOut;
let thisNode;
stack.push(root);
while (stack.length){
// 1
thisNode = stack.pop();
if(thisNode == null) {
continue;
}
// 2
if (thisNode.right != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
stack.push(thisNode.right);
}
stack.push(thisNode);
if (thisNode.left != null && !(lastOut != null && lastOut == thisNode.left) && !(lastOut != null && lastOut.right == null)) {
stack.push(thisNode.left);
}
// 3
// thisNode = stack[stack.length - 1];
if( thisNode.left == null || thisNode.left == lastOut || (lastOut && lastOut.right == null)) {
lastOut = stack.pop();
traversal.push(lastOut.val);
}
}
return traversal;
};
后序
左右中
/**
* Recursive 递归
*/
var postorderTraversal = function(root) {
var r = [];
if(!root) return [];
if(root.left)
r = r.concat(postorderTraversal(root.left));
if(root.right)
r = r.concat(postorderTraversal(root.right));
r.push(root.val);
return r;
};
/**
* Recursive 递归2
*/
var postorderTraversal = function(root) {
let result = [];
helper(result, root);
return result;
};
var helper = function(r, root) {
if(root != null) {
helper(r, root.left);
helper(r, root.right);
r.push(root.val);
}
}
/**
* iteratively 迭代
*/
var postorderTraversal = function(root) {
var treeNodeStack = [];
var node = root;
var lastVisit = root;
var res = [];
while (node != null || treeNodeStack.length>0) {
while (node != null) {
treeNodeStack.push(node);
node = node.left;
}
node = treeNodeStack[treeNodeStack.length-1];
if (node.right == null || node.right == lastVisit) {
res.push(node.val);
treeNodeStack.pop();
lastVisit = node;
node = null;
} else {
node = node.right;
}
}
return res;
};
网友评论