Java 이진 트리의 재귀 및 비재귀 순회 방법은 무엇입니까?

머리말

이진 트리의 순회 방법은 선순 순회, 순순 순회, 후속 순회, 수준순 순회로 구분됩니다.

1. 재귀 순회

재귀의 경우 재귀의 세 가지 요소에 대해 이야기해야 합니다. 선주문 순회를 예로 들어

재귀 입력 매개변수 및 반환 값

값을 인쇄해야 하기 때문입니다. ​선주문 순회 노드의 매개변수이므로 목록의 노드 값을 전달해야 합니다. 이 외에도 데이터를 처리할 필요가 없으며 반환 값이 필요하지 않으므로 반환됩니다. 재귀 함수 유형은 void입니다. 코드는 다음과 같습니다.

public void preorder(TreeNode root, List<Integer> result)

종료 조건 결정

재귀 과정에서 재귀는 어떻게 종료됩니까? 물론 현재 순회하는 노드가 비어 있으면 현재 수준은 다음과 같습니다. 재귀가 곧 끝나기 때문에 현재 순회하는 노드가 비어 있으면 바로 리턴

if (root == null) return;

Single-layer loop Logic

선순서 순회는 중간 순서와 왼쪽 순서이므로 단일 수준 재귀의 논리는 다음과 같습니다. 코드는 다음과 같습니다.

result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);//先保存中间节点
        preorder(root.left, result); //处理左边节点
        preorder(root.right, result); //处理右边节点
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list); //先处理左边节点
        list.add(root.val);       //保存中间当前的节点
        inorder(root.right, list);//先处理右边节点
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);  //先处理左边节点
        postorder(root.right, list); //再处理右边节点
        list.add(root.val);          //保存最后  
    }
}

2. 비반복 순회

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        if (root == null) return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) { //先将右孩子入栈，因为它在最后
                stack.push(node.right);
            }
            if (node.left != null) { //左孩子入栈再出栈
                stack.push(node.left);
            }
        }
        return res;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            //如果可以，一直往左下探
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop(); //弹出来的肯定是叶子节点或中间节点
                res.add(cur.val); //将这个节点加入list
                cur = cur.right; //查看当前节点是否有右节点，如果右，肯定是中间节点，如果没有，就是叶子节点，继续弹出就可以
            }
        }
        return res;
    }
}
//后序遍历
//再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) stack.push(node.left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node.right != null) stack.push(node.right);// 空节点不入栈 
        }
        Collections.reverse(res); // 将结果反转之后就是左右中的顺序了
        return res;
    }
}

3. 이진 트리의 통합 반복 방법

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

위 내용은 Java 이진 트리의 재귀 및 비재귀 순회 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!