二叉树的练习题

​1. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的前序遍历。

输入：{1,#,2,3}

返回值：[1,2,3]

思路1：二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

• 终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
• 返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
• 子问题： 每个子问题优先访问这棵子树的根节点，然后递归进入左子树和右子树。

思路2：使用辅助栈来存放每次遍历的根节点，弹出栈顶元素，然后判断该元素是否有左右子节点，有的话的加入栈中，优先加入右节点。同样也要先判断树是否为空，空树不遍历。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
 
public class Main {
    /**
     * 递归方法
     * @param root
     * @return
     */
    public int[] preorderTraversal(TreeNode root) {
        // write code here
        // 添加遍历结果的数组
        List list = new ArrayList();
        preOrder(list, root);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
 
    public void preOrder(List list, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preOrder(list, root.left);
        preOrder(list, root.right);
    }
 
 
    /**
     * 迭代方法
     * @param root
     * @return
     */
    public int[] preorderTraversal2 (TreeNode root) {
        // write code here
        // 判空
        if(root == null) {
            return new int[0];
        }
        // 存放树节点的集合
        List list = new ArrayList();
        // 辅助栈
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            // 先右树再左树，因为栈是先进先出的
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null) {
                stack.push(node.left);
            }
        }
        // 结果集
        int[] result = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

---

2. 二叉树的中序遍历

给定一个二叉树的根节点root，返回它的中序遍历结果。

输入：{1,2,#,#,3}

返回值：[2,3,1]

import java.util.*;
 
public class Main {
    /**
     * 迭代方法
     * @param root
     * @return
     */
    public int[] inorderTraversal(TreeNode root) {
        // write code here
        List list = new ArrayList();
        inOrder(root, list);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
 
    public void inOrder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
 
    /**
     * 递归方法
     * @param root
     * @return
     */
    public int[] inorderTraversal2 (TreeNode root) {
        // write code here
        List list = new LinkedList<>();
        if (root == null) {
            return new int[0];
        }
        Stack stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

---

3. 二叉树的后序遍历

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

import java.util.*;
public class Main {
    /**
     * 递归
     * @param root
     * @return
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List list = new ArrayList();
        postOrder(list, root);
        int[] result = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
 
    public void postOrder(List list, TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(list, root.left);
        postOrder(list, root.right);
        list.add(root.val);
    }
 
    /**
     * 迭代
     * @param root
     * @return
     */
    public int[] postorderTraversal2 (TreeNode root) {
        // write code here
        List list = new LinkedList<>();
        if(root == null) {
            return new int[0];
        }
        Stack stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 弹出栈顶
            TreeNode node = stack.pop();
            if (node.right == null || node.right == pre) {
                list.add(node.val);
                pre = node;
            } else {
                stack.push(node);
                root = node.right;
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

---

​​​​​​​

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[[3],[9,20],[15,7]]

public class Solution {
    public ArrayList> levelOrder (TreeNode root) {
        // write code here
        ArrayList> list = new ArrayList();
        if(root == null) {
            return list;
        }
        // 队列存储
        Queue queue = new LinkedList<>();
        // 先进头节点放入队列中
        queue.add(root);
        while(!queue.isEmpty()) {
            // 记录二叉树的某一行
            ArrayList level = new ArrayList();
            int size = queue.size();
            // 每层节点多少，队列大小就是多大
            for(int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                // 将出队的节点加入行中
                level.add(cur.val);
                if(cur.left != null) {
                    // 若左孩子存在，将存入左孩子的左右孩子作为下一层
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    // 若右孩子存在，将存入右孩子的左右孩子作为下一层
                    queue.offer(cur.right);
                }
            }
            // 每一层加入结果集中
            list.add(level);
        }
        return list;
    }
}

活动地址：CSDN21天学习挑战赛