今天学了二叉树结点表示法,建树代码如下。
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(val);
}
}
我们建一棵树,然后使用递归的方式前中后序遍历(preOrder、inOrder、postOrder),再使用非递归方式遍历(traversal)。
public class Test {
public static void main(String[] args) {
TreeNode root = new TreeNode(
1,
new TreeNode(2, new TreeNode(4, null, null), null),
new TreeNode(3, new TreeNode(5, null, null), new TreeNode(6, null, null))
);
preOrder(root);
inOrder(root);
postOrder(root);
traversal(root);
}
建的树如下:
递归深度遍历:
/**
* 前序
*/
public static void preOrder(TreeNode t){
if(t == null) return;
System.out.println(t.val);
preOrder(t.left);
preOrder(t.right);
}
/**
* 中序
*/
public static void inOrder(TreeNode t){
if(t == null) return;
inOrder(t.left);
System.out.println(t.val);
inOrder(t.right);
}
/**
* 后序
*/
public static void postOrder(TreeNode t){
if(t == null) return;
postOrder(t.left);
postOrder(t.right);
System.out.println(t.val);
}
非递归的方式
使用以下代码可以通用前中后序的遍历。
/**
* 一套代码通用遍历,改造后序遍历
*/
public static void traversal(TreeNode t){
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pop = null;
while(t != null || !stack.isEmpty()){
if(t != null){
//左子树还没处理
System.out.println("前序: " + t.val);
stack.push(t);
t = t.left;
}
else{
TreeNode peek = stack.peek();
if(peek.right == null){
//右子树为空
System.out.println("中序: " + peek.val);
pop = stack.pop();
System.out.println("后序: " + pop.val);
}
else if(peek.right == pop){
//右子树处理完成
pop = stack.pop();
System.out.println("后序: " + pop.val);
}
else{
//右子树还没处理
System.out.println("中序: " + peek.val);
t = peek.right;
}
}
}
}
使用以上知识解决如下题目:
1、144. 二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pop = null;
while(root != null || !stack.isEmpty()){
if(root != null){
list.add(root.val);
stack.push(root);
root = root.left;
}
else{
TreeNode peek = stack.peek();
if(peek.right == null || peek.right == pop){
pop = stack.pop();
}
else{
root = peek.right;
}
}
}
return list;
}
}
2、94. 二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pop = null;
while(root != null || !stack.isEmpty()){
if(root != null){
stack.push(root);
root = root.left;
}
else{
TreeNode peek = stack.peek();
if(peek.right == null){
list.add(peek.val);
pop = stack.pop();
}
else if(peek.right == pop){
pop = stack.pop();
}
else{
list.add(peek.val);
root = peek.right;
}
}
}
return list;
}
}
3、145. 二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode pop = null;
while(root != null || !stack.isEmpty()){
if(root != null){
stack.push(root);
root = root.left;
}
else{
TreeNode peek = stack.peek();
if(peek.right == null || peek.right == pop){
pop = stack.pop();
list.add(peek.val);
}
else{
root = peek.right;
}
}
}
return list;
}
}