二叉树的前中后序遍历

在进行二叉树的前中后序遍历的时候，要先明白前中后序遍历的顺序：
前：根->左->右
中：左->根->右
后：左->右->根
下面实现的两种方法：一种是以递归的形式实现。一种是以迭代的方式实现，两者的区别是迭代显示的掉用了一个栈。
在使用栈的时候利用栈的弹出特点，进行一个深度的遍历，例如递归调用

preorder(node.left,list); //一直往下深入，直到为叶子节点 preorder(node.right,list); //在左左边深入到叶子开始弹出的时候再往右子树开始

具体步骤看中序遍历代码的注释

前序遍历

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    //迭代
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }
    /**
     * 递归
     */
     public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer> list = new ArrayList<>();
         preorder(root,list);
         return list;
     }
     void preorder(TreeNode node,List<Integer> list){
         if(node==null) return;
         list.add(node.val);
         preorder(node.left,list);
         preorder(node.right,list);
     }
}

中序遍历

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
/**
 * 中序遍历：左->根->右
 * 判断根节点有没有左子树
 */
class Solution {
    /**
     * 使用迭代
     */
     public List<Integer> inorderTraversal(TreeNode root){
         //用来保存值
         List<Integer> res = new ArrayList<>();
         //显示的栈用来走到最深处再弹出当前root
         Deque<TreeNode> stack = new LinkedList<>();
         while(root!=null || !stack.isEmpty()){
             //走到左节点最深处
             while(root!=null){
                 stack.push(root);
                 root = root.left;
             }
             //开始弹出 - 将栈顶元素放入集合中
             root = stack.pop();
             res.add(root.val);
             root = root.right;
         }
         return res;
     }
    // 使用递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new  ArrayList<>();
        de(root,res);
        return res;
    }
    public void de(TreeNode node,List<Integer> res){
        // 判断是否为空，为空就返回
        if(node == null){
            return;
        }
        // 不为空的话继续遍历改节点的孩子直到为空退出
        de(node.left,res);
        // 当遍历到左边的底的时候开始添加元素
        res.add(node.val);
        de(node.right,res);
    }
}

后序遍历

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //迭代
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode pre = null;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right==null || root.right==pre ){
                res.add(root.val);
                pre = root;
                root = null; //表明访问过
            }else{
                stack.push(root); 
                root = root.right;
            }
        }
        return res;
    }
}

二叉搜索树的验证

二叉搜索树左子树的值都比根节点小，右子树的值都比根节点大；

class Solution {
    public boolean isValidBST(TreeNode root) {
        return recur(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    boolean recur(TreeNode node,long l,long r){
        if(node==null){return true;}
        if(node.val <= l || node.val>=r){
            return false;
        }
        return recur(node.left,l,node.val) && recur(node.right,node.val,r);
    }
}

重建二叉树(根据前中序）

前：根->左->右
中：左->根->右
例子

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

思路：根据前序的根节点，找出中序遍历中根节点的索引，索引前面为左子树，后面为右子树，一直递归遍历下去；
通过map来保存中序遍历中的值和索引，通过值找到索引。

// 1:前序中的根索引 2:中序中左孩子开始 3:中序中左边孩子结束
tree.left = recur(root_ind+1,left_ind,i-1); // 1. 参数根=当前根索引加上中序中根索引的前面元素个数+1再减去之前加上的元素(left) tree.right = recur(root_ind+i+1-left_ind,i+1,right_ind);

class Solution {
    //用来保存中序遍历中查找根节点的索引
    HashMap<Integer,Integer> map = new HashMap<>();
    int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        int len = inorder.length;
        for(int i = 0;i<len;i++){
            map.put(inorder[i],i);
        }
        return recur(0,0,len-1);
    }
    TreeNode recur(int root_ind,int left_ind,int right_ind){
        if(left_ind>right_ind) return null;  // 终止条件
        TreeNode tree = new TreeNode(preorder[root_ind]); // 根节点
        int i = map.get(preorder[root_ind]); // 获取在中序数组中根节点的索引位置
        // 1:前序中的根索引 2:中序中左孩子开始 3:中序中左边孩子结束
        tree.left = recur(root_ind+1,left_ind,i-1); 
        // 1. 参数根=当前根索引加上中序中根索引的前面元素个数+1再减去之前加上的元素(left)
        tree.right = recur(root_ind+i+1-left_ind,i+1,right_ind);
        return tree;
    }
}

路径总和

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

在路径和中，把当前值放到集合中的时候，如果匹配不正确，需要将元素进行删除。

class Solution {
    //官方
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
    //自己写的
    List<List<Integer>> res = new ArrayList<>(); 
    List<Integer> cur = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root,int targetSum) {
        dfs(root,targetSum);
        return res;
    }
    void dfs(TreeNode node, int targetSum){
        if(node==null){
            return;
        }
        cur.add(node.val);
        targetSum -= node.val;
        if(node.left==null && node.right==null && 0==targetSum){
            res.add(new ArrayList<Integer>(cur));
            cur.remove(cur.size()-1);
            return;
        }
        dfs(node.left,targetSum);
        dfs(node.right,targetSum);
        cur.remove(cur.size()-1);
    }
}

数据结构与算法

二叉树相关