編程導(dǎo)航算法村第七關(guān) | 二叉樹(shù)的遍歷

前序遍歷（遞歸）

 public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        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);
    }

前序遍歷（迭代）

• 先迭代到樹(shù)的最底層，左左端的元素，然后彈出棧，訪問(wèn)他的右節(jié)點(diǎn)

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

        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node!= null) {
                result.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return result;
    }

中序遍歷（迭代）

 public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
        return result;
    }

后續(xù)遍歷（反轉(zhuǎn)法）

• 后續(xù)遍歷相當(dāng)于在前序遍歷的基礎(chǔ)上，先訪問(wèn)右節(jié)點(diǎn)再訪問(wèn)左節(jié)點(diǎn)，最后翻轉(zhuǎn)

 public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                result.add(node.val);
                node = node.right;
            }
            node = stack.pop();
            node = node.left;
        }
        Collections.reverse(result);
        return result;
    }

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-624885.html

到了這里，關(guān)于編程導(dǎo)航算法村第七關(guān) |二叉樹(shù)的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！