作者：黄董一叶知秋_821 | 来源：互联网 | 2023-10-17 21:00
二叉树的前序遍历（递归版）：
public ArrayList inOrder(TreeNode root ){
ArrayList result = new ArrayList();
if(root == null){
return result;
}
result.add(root.val);
inOrder(root.left);+
inOrder(root.right);
return result;
}
二叉树的中序遍历（递归版）：
public ArrayList inOrder(TreeNode root ){
ArrayList result = new ArrayList();
if(root == null){
return result;
}
inOrder(root.left);
result.add(root.val);
inOrder(root.right);
return result;
}
二叉树的后续遍历（递归版）：
public ArrayList inOrder(TreeNode root ){
ArrayList result = new ArrayList();
if(root == null){
return result;
}
inOrder(root.left);
inOrder(root.right);
result.add(root.val);
return result;
}
递归版总结：
其实就是添加节点的地方不同
前序遍历：添加节点就是在递归之前添加；
中序遍历：添加节点在左右节点递归之间；
后序遍历：添加节点是在左右节点递归之后；
二叉树的前序遍历（迭代版）：
public ArrayList preOrder(TreeNode root){
ArrayList result= new ArrayList();
Stack stack = new Stack();
if(root == null){
return result;
}
if(root != null){
stack.push(root);
result.add(root.val);
root=root.left;
}else{
root=stack.pop();
root=root.right;
}
return result;
}
二叉树中序遍历（迭代版）:
public ArrayList inOrder(TreeNode root){
ArrayList result = new ArrayList();
Stack stack = new Stack();
if(root == null){
return result;
}
while(root != null || !stack.isEmpty()){
if(root != null){
stack.push(root);
root=root.left;
}else{
root= stack.pop();
result.add(root.val);
root= root.right;
}
}
return result;
}
二叉树后序遍历（迭代版）:
最开始以为他很难，当你理解前两个之后，就会发现他跟前序遍历很像！
public ArrayList postTreeNode(TreeNode root){
Stack midstack = new Stack();
Stack resultstack= new Stack() ;
ArrayList result = new ArrayList();
while(root != null || !midstack.isEmpty()){
if(root != null){
midstack.push(root);
resultstack.push(root);
root=root.right;
}else{
root=midstack.pop();
root=root.left;
}
}
while(resultstack.size() > 0){
TreeNode temp = resultstack.pop();
result.add(temp.val);
}
return result;
}
京公网安备 11010802041100号