[移动开发]二叉树遍历（前中后）

二叉树定义：

public class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
	public TreeNode(){}
	public TreeNode(int value) {
		this.value = value;
	}
	public TreeNode(int vlaue, TreeNode left, TreeNode right) {
		this.value = value;
		this.left = left;
		this.right = right;
	}
}

前序遍历：

递归

public List<Integer> preorderTraversaOfRecursion(TreeNode root) {
	if(root == null){
		return new ArrayList<>();
	}
	List<Integer> result = new ArrayList<>();
	this.preorderOfRecursion(result, root);
	return result;
}

private void preorderOfRecursion(List<Integer> result, TreeNode root) {
	if (root == null) {
		return;
	}
	result.add(root.value);
	preorderOfRecursion(root.left);
	preorderOfRecursion(root.right);
}

遍历

public List<Integer> preorderTraversalOfIterator(TreeNode root){
	if (root == null) {
		return new ArrayList<>();
	}
	
	List<Integer> result = new ArrayList<>();
	Stack<TreeNode> stack = new Stack<>();
	while (root != null || !stack.isEmpty()){
		while(root != null) {
			result.add(root.value);
			root = root.left;
		}
		root = stack.pop();
		root = root.right;
	}
}	

中序遍历：

递归

public List<Integer> inorderTraversalOfRecursion(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        inorderOfRecursion(result, root);
        return result;
    }

    private void inorderOfRecursion(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }

        inorderOfRecursion(result, root.left);
        result.add(root.value);
        inorderOfRecursion(result, root.right);
    }

遍历

public List<Integer> inorderTraversalOfIterator(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            result.add(root.value);
            root = root.right;
        }

        return result;
    }

后序遍历：

递归

 public List<Integer> postorderTraversalOfRecursion(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        this.postorderOfRecursion(result, root);
        return result;
    }

    private void postorderOfRecursion(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }

        postorderOfRecursion(result, root.left);
        postorderOfRecursion(result, root.right);
        result.add(root.value);
    }

遍历

public List<Integer> postorderTraversalOfIterator(TreeNode root) {
	if (root == null) {
		return new ArrayList<>();
	}
	
	List<Integer> result = new ArrayList<>();
	Stack<TreeNode> stack = new Stack<>();
	TreeNode preNode = null;
	while( root != null || stack.isEmpty()){
		while (root != null) {
			stack.push(root);
			root = root.left;
		}

		root = root.pop();
		if (root.right == null || root.right == preNode) {
			result.add(root.value);
			preNode = root;
			root = null;
		} else {
			root = stack.pop();
			root = root.right;
		}
	}
}