【資料結構】樹前序周遊、中序周遊、後序周遊的遞歸與非遞歸方法java

目錄

• 1.遞歸方法
• 2.非遞歸先序
• 3.非遞歸中序
• 4.非遞歸後序
• 5.層序周遊
• 6.路徑總和

1.遞歸方法

package test;

import java.util.Stack;

class Node {
	int val;
	Node left = null;
	Node right = null;
	Node(int val) {
		this.val = val;
	}
}
public class Tree {
	// 遞歸先序
	public void preRootTraversalR(Node root) {
		if (root == null) {
			return;
		}
		System.out.println(root.val);
		preRootTraversalR(root.left);
		preRootTraversalR(root.right);
	}


	public static void main(String[] args) {
		//      1
		//     2  3
		//    4 5 6 7
		//       8
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node3.left = node6;
		node3.right = node7;
		node6.right = node8;
		Tree tree = new Tree();
		tree.after(node1);
	}
}
           

2.非遞歸先序

方法一：

public void preRootTraversal(Node root) {
		if (root == null) {
			return;
		}
		Stack stack = new Stack<>();
		Node temp = root;
		while (temp != null || !stack.empty()) {
			while (temp != null) {
				System.out.println(temp.val);
				stack.add(temp);
				temp = temp.left;
			}
			temp = stack.pop().right;
		}
	}
           

方法二：

public void query(Node root){//非遞歸先序
		if (root==null) return;
		Stack<Node> stack=new Stack<>();
		Node temp =root;
		stack.push(temp);
		while(!stack.empty()){
			temp=stack.pop();
			System.out.println(temp.val);
			if (temp.right!=null) 
				stack.push(temp.right);	
			if (temp.left!=null) 
				stack.push(temp.left);
		}
	}
           

3.非遞歸中序

方法一：

public void mid(Node root) {
		if (root == null) {
			return;
		}
		Stack stack = new Stack<>();
		Node temp = root;
		while (temp != null || !stack.empty()) {
			while (temp != null) {
				stack.push(temp);
				temp = temp.left;
			}
			Node peek = stack.pop();
			System.out.println(peek.val);
			temp = peek.right;
		}
	}
           

方法二：

public void query(Node root){//非遞歸中序
		if (root==null) return;
		Stack<Node> stack=new Stack<>();
		Node temp =root;
		while(!stack.empty()||temp!=null){
			if(temp!=null){
				stack.push(temp);
				temp=temp.left;
			}else{
				System.out.println(stack.peek().val);
				temp=stack.pop().right;
			}
		}
	}
           

4.非遞歸後序

public void query(Node root){//後序  左 右 根
		Stack<Node> stack=new Stack<>();
		Stack<Node> ret=new Stack<>();//存儲最終的結果
		Node temp =root;
		stack.push(temp);
		while(!stack.empty()){
			temp=stack.pop();
			ret.push(temp);
			if (temp.left!=null) {
				stack.push(temp.left);
			}
			if (temp.right!=null) {
				stack.push(temp.right);
			}
		}
		while(!ret.empty()){
			temp=ret.pop();
			System.out.println(temp.val);
		}

	}
           

5.層序周遊

使用隊列

public void query(Node root){//層序周遊
		if (root==null) return;
		Queue<Node> queue=new LinkedList<Node>();
		queue.add(root);
		while(!queue.isEmpty()){
			int len=queue.size();
			while(len>=0){
				Node node=queue.poll();
				System.out.println(node.val);
				if (node.left!=null) 
					queue.add(node.left);
				if (node.right!=null) 
				len--;
			}
		}
	}
           

6.路徑總和

112.路徑總和

import java.util.*;
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        sum-=root.val;
        if(root.left==null&&root.right==null){
            return sum==0;
        }
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }
}
           

113.路徑總和II

import java.util.*;
class Solution {
    List<List<Integer>> list =new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) return list;
        ArrayList<Integer> stack=new ArrayList<>();
        core(root,sum,stack);
        return list;
    }
    public void core(TreeNode root, int sum, ArrayList<Integer> stack) {
        if(root==null) return;
        if(sum==root.val&&root.left==null&&root.right==null){
            ArrayList<Integer> arr=new ArrayList<>();
            for(int i:stack){
                arr.add(i);
            }
            arr.add(root.val);
            list.add(arr);
        }
        stack.add(root.val);
        core(root.left,sum-root.val,stack);
        core(root.right,sum-root.val,stack);
        stack.remove(stack.size()-1);
    }
}