94. 144. 145. 二叉树的前中后序遍历模板
/*
* @Author: Goog Tech
* @Date: 2020-07-27 10:56:38
* @Description: #94 #144 #145: Binary Tree Traversal Template
* @FilePath: \leetcode-googtech\#94 #144 #145 Binary Tree Traversal Template\Template.java
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 前序遍历:递归法
*/
List <Integer > result = new ArrayList <>();
public List <Integer > preorderTraversal (TreeNode root ) {
if (root == null ) return new ArrayList <Integer >();
result .add (root .val );
preorderTraversal (root .left );
preorderTraversal (root .right );
return result ;
}
/**
* 中序遍历:递归法
*/
List <Integer > result = new ArrayList <>();
public List <Integer > inorderTraversal (TreeNode root ) {
if (root == null ) return new ArrayList <>();
inorderTraversal (root .left );
result .add (root .val );
inorderTraversal (root .right );
return result ;
}
/**
* 后续遍历:递归法
*/
List <Integer > result = new ArrayList <>();
public List <Integer > postorderTraversal (TreeNode root ) {
if (root == null ) return new ArrayList <>();
postorderTraversal (root .left );
postorderTraversal (root .right );
result .add (root .val );
return result ;
}
/**
* 前序遍历:迭代法一
*/
public List <Integer > preorderTraversal (TreeNode root ) {
// 判断头节点是否为空
if (root == null ) return new ArrayList <Integer >();
// 声明辅助栈及结果链表
TreeNode currentNode = root ;
List <Integer > result = new ArrayList <>();
Stack <TreeNode > stack = new Stack <>();
// 循环遍历辅助栈
while (currentNode != null || !stack .isEmpty ()) {
// 将左孩子节点压入栈中并存储到结果链表中
while (currentNode != null ) {
stack .push (currentNode );
result .add (currentNode .val );
currentNode = currentNode .left ;
}
// 更新当前节点为其右孩子节点,进入下一个循环
currentNode = stack .pop ();
currentNode = node .right ;
}
return result ;
}
/**
* 中序遍历:迭代法一
*/
public List <Integer > inorderTraversal (TreeNode root ) {
// 判断头节点是否为空
if (root == null ) return new ArrayList <>();
// 声明辅助栈及结果链表
TreeNode currentNode = root ;
List <Integer > result = new ArrayList <>();
Stack <TreeNode > stack = new Stack <>();
// 循环遍历辅助栈
while (currentNode != null || !stack .isEmpty ()) {
// 将左孩子节点压入栈中
while (currentNode != null ) {
stack .push (currentNode );
currentNode = currentNode .left ;
}
// 出栈并将其存储到结果链表中
currentNode = stack .pop ();
result .add (currentNode .val );
// 更新当前节点为右孩子节点,进入下一个循环
currentNode = currentNode .right ;
}
return result ;
}
/**
* 后序遍历:迭代法一
* 在后序遍历中每个节点需要访问两次,即当遍历完左子树后需要访问当前节点,
* 之后遍历完右子树后还需要访问当前节点,但只有在第二次访问时才处理当前节点.
*/
public List <Integer > postorderTraversal (TreeNode root ) {
// 判断头节点是否为空
if (root == null ) return new ArrayList <Integer >();
// previousNode为当前节点的前一个节点,用于区分之前的节点是否被访问过
TreeNode currentNode = root ;
TreeNode previousNode = null ;
// 声明辅助栈及结果链表
List <Integer > result = new ArrayList <>();
Stack <Integer > stack = new Stack <>();
// 循环遍历辅助栈
while (currentNode != null || !stack .isEmpty ()) {
while (currentNode != null ) {
stack .push (currentNode );
currentNode = currentNode .left ;
}
// 更新当前节点为用户栈出栈节点
currentNode = stack .pop ();
// 当右孩子为空及右孩子被访问过时,访问当前节点,更新当前节点为空,为下一步的出栈作准备
if (currentNode .right == null || currentNode .right == previousNode ) {
result .add (currentNode .val );
previousNode = currentNode ;
currentNode = null ;
}else {
// 更新当前节点为右孩子节点
stack .push (currentNode );
currentNode = currentNode .right ;
}
}
return result ;
}
/**
* 前序遍历:迭代法二
*/
public List <Integer > preorderTraversal (TreeNode root ) {
// 判断头节点是否为空
if (root == null ) return new ArrayList <Integer >();
TreeNode currentNode = null ;
// 初始化辅助栈及结果链表
List <Integer > result = new ArrayList <>();
Stack <TreeNode > stack = new Stack <>();
// 将根节点压入栈中
stack .push (root );
// 重复操作:将栈中节点弹出并存储到list中,然后将右及左节点压入栈中
while (!stack .isEmpty ()) {
currentNode = stack .pop ();
result .add (currentNode .val );
// 根据Stack的特性,即FILO可知先弹出左节点
if (currentNode .right != null ) stack .push (currentNode .right );
if (currentNode .left != null ) stack .push (currentNode .left );
}
return result ;
}
/**
* 后续遍历:迭代法二
* 利用先序的遍历顺序:root=>left->right,先将先序遍历更改为:root->right->left
* 然后反转List,得到的结果的顺序即为:left->right->root
*/
public List <Integer > postorderTraversal (TreeNode root ) {
// 判断头节点是否为空
if (root == null ) return new ArrayList <Integer >();
TreeNode currentNode = null ;
// 初始化辅助栈及结果链表
List <Integer > result = new ArrayList <>();
Stack <TreeNode > stack = new Stack <>();
// 将根节点压入栈中
stack .push (root );
// 重复操作:将栈中节点弹出并存储到list中,然后将左及右节点压入栈中
while (!stack .isEmpty ()) {
currentNode = stack .pop ();
// 逆序添加节点值
result .add (0 ,currentNode .val );
// 根据Stack的特性,即FILO可知先弹出右节点
if (currentNode .left != null ) stack .push (currentNode .left );
if (currentNode .right != null ) stack .push (currentNode .right );
}
return result ;
}
}
'''
@Author: Goog Tech
@Date: 2020-07-27 10:56:50
@Description: #94 #144 #145: Binary Tree Traversal Template
@FilePath: \leetcode-googtech\#94 #144 #145 Binary Tree Traversal Template\Template.py
'''
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution (object ):
'''
前序遍历: 递归法
'''
def preorderTraversal (self , root ):
return [] if root is None else [root .val ] + self .preorderTraversal (
root .left ) + self .preorderTraversal (root .right )
'''
中序遍历: 递归法
'''
def inorderTraversal (self , root ):
return [] if root is None else self .inorderTraversal (
root .left ) + [root .val ] + self .inorderTraversal (root .right )
'''
后序遍历: 递归法
'''
def postorderTraversal (self , root ):
return [] if root is None else self .postorderTraversal (
root .left ) + self .postorderTraversal (root .right ) + [root .val ]
'''
前序遍历: 迭代法
'''
def preorderTraversal (self , root ):
# 判断根节点是否为空
if root is None : return []
# 初始化辅助栈及结果列表
stack , result = [root ], []
# 重复操作:将栈中根节点弹出并存储到list中,然后将右及左节点压入栈中
while stack :
root = stack .pop ()
result .append (root .val )
# 根据Stack的特性,即FILO可知先弹出左节点
if root .right is not None :
stack .append (root .right )
if root .left is not None :
stack .append (root .left )
return result
'''
中序遍历: 迭代法
'''
def inorderTraversal (self , root ):
# 初始化辅助栈及结果列表
result , stack , currentNode = [], [], root
# 判断头节点是否为空
if root is None : return result
currentNode = root
# 遍历辅助栈
while stack or currentNode :
# 遍历左孩子节点并将其依次压入栈中,直到为空然后进入操作2
if currentNode is not None : # 操作1
stack .append (currentNode )
currentNode = currentNode .left
# 弹出栈顶元素,若其有右孩子,则将右孩子节点压入栈中,随后重复操作1
else : # 操作2
currentNode = stack .pop ()
result .append (currentNode .val )
currentNode = currentNode .right
return result
'''
后续遍历: 迭代法
前序的遍历顺序是“根左右”,而后序是“左右根”
所以可以先模仿前序生成“根右左”,然后再反转就是“左右根”咯
'''
def postorderTraversal (self , root ):
# 判断根节点是否为空
if root is None : return []
# 初始化辅助栈及声明用于存储结果的列表
result , stack , current = [], [root ], root
# 重复操作:将栈中根节点弹出并存储到list中,然后将左及右节点依次压入栈中
while stack :
current = stack .pop ()
result .append (current .val )
# 根据Stack的特性,即FILO可知先弹出右节点
if current .left is not None :
stack .append (current .left )
if current .right is not None :
stack .append (current .right )
# 反转列表
return result [::- 1 ]