鏈接：力扣94-二叉樹(shù)中序遍歷

鏈接：力扣144-二叉樹(shù)前序遍歷

鏈接：力扣145-二叉樹(shù)后序遍歷

樹(shù)的結(jié)構(gòu)

 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }

================================================

鏈接：力扣94-二叉樹(shù)中序遍歷

遞歸

思路

1、確定返回值和方法參數(shù)：需要集合來(lái)存放樹(shù)各節(jié)點(diǎn)的值，最后打印出來(lái)，所以需要一個(gè)list集合作為參數(shù)，不斷迭代；除此之外不需要有返回值

2、確定終止條件：當(dāng)前節(jié)點(diǎn)為空時(shí)，則需要結(jié)束本次方法調(diào)用（結(jié)束本次遞歸），用return

3、確定單次遞歸邏輯：中序遍歷，左中右 處理，對(duì)root的處理就是加入到集合中

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> list){
        // 當(dāng)前傳入的root為null結(jié)束本方法的執(zhí)行，繼續(xù)下面方法的執(zhí)行
        if(root == null) return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

非遞歸

思路

1、終止條件：棧為空 且 cur節(jié)點(diǎn)為空

2、如果左孩子一直不為空，則需要一直入棧

3、左孩子為空后，則開(kāi)始pop節(jié)點(diǎn)（入集合），pop出的節(jié)點(diǎn)也要看其左孩子，所以cur要指向pop出的節(jié)點(diǎn)，繼續(xù)判斷其左孩子

class Solution {
    public List<Integer> inorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        TreeNode cur = root;
        // 這里除了判空，也有可能棧空了，但是右節(jié)點(diǎn)還沒(méi)有處理（未入棧）
        while(!stack.isEmpty() || cur != null){
            // 如果左孩子一直存在，則要一路把左孩子都存進(jìn)去，直到cur為空
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            // cur為空時(shí)，則說(shuō)明左邊已經(jīng)循環(huán)到低了，可以開(kāi)始pop并入集合
            // 也需要開(kāi)始處理右節(jié)點(diǎn)，右節(jié)點(diǎn)處理也是要一路把左節(jié)點(diǎn)先存進(jìn)去，重復(fù)上述步驟
            // 所以要將右節(jié)點(diǎn)命為cur，也就是要處理的節(jié)點(diǎn)
            }else{
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }
}

鏈接：力扣144-二叉樹(shù)前序遍歷

遞歸

思路

1、確定返回值和方法參數(shù)：需要集合來(lái)存放樹(shù)各節(jié)點(diǎn)的值，最后打印出來(lái)，所以需要一個(gè)list集合作為參數(shù)，不斷迭代；除此之外不需要有返回值

2、確定終止條件：當(dāng)前節(jié)點(diǎn)為空時(shí)，則需要結(jié)束本次方法調(diào)用（結(jié)束本次遞歸），用return

3、確定單次遞歸邏輯：前序遍歷，中左右 處理，對(duì)root的處理就是加入到集合中，對(duì)左右節(jié)點(diǎn)處理，就是不斷遞歸

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

非遞歸

思路

1、先讓root入棧，接著pop出來(lái)，定義為node，先把node.val添加到集合中，再去判斷其是否有左右孩子，一定先右后左，出棧順序相反

2、循環(huán)終止條件：棧為空則說(shuō)明所有節(jié)點(diǎn)已經(jīng)處理完畢

class Solution {
    public List<Integer> preorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        stack.push(root);
        // 這里除了判空，不需要其它條件，即使出?？樟?，后面還會(huì)有節(jié)點(diǎn)push進(jìn)去
        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;
    }
}

鏈接：力扣145-二叉樹(shù)后序遍歷

遞歸

思路

1、確定返回值和方法參數(shù)：需要集合來(lái)存放樹(shù)各節(jié)點(diǎn)的值，最后打印出來(lái)，所以需要一個(gè)list集合作為參數(shù)，不斷迭代；除此之外不需要有返回值

2、確定終止條件：當(dāng)前節(jié)點(diǎn)為空時(shí)，則需要結(jié)束本次方法調(diào)用（結(jié)束本次遞歸），用return

3、確定單次遞歸邏輯：后序遍歷，左右中 處理，對(duì)**root（傳入節(jié)點(diǎn)）**的處理就是加入到集合中，對(duì)左右節(jié)點(diǎn)處理，就是不斷遞歸

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root,res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> list){
        if(root == null) return;
        postorder(root.left, list);
        postorder(root.right,list);
        list.add(root.val);
    }
}

非遞歸

思路

入棧順序中、左、右；出棧順序：中、右、左；翻轉(zhuǎn)順序：左、右、中文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-608269.html

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);
            }
        }
        // 入棧順序中、左、右；出棧順序：中、右、左；翻轉(zhuǎn)順序：左、右、中
        Collections.reverse(res);
        return res;
    }
}

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