二叉树中的深搜

• 🎥 个人主页：Dikz12
• 🔥个人专栏：算法(Java)
• 📕格言：吾愚多不敏，而愿加学
• 欢迎大家👍点赞✍评论⭐收藏

目录

1. 计算布尔二叉树的值 

 1.1 题目描述

1.2 题解

1.3 代码实现 

 2. 求根节点到叶子节点数字之和

 2.1 题目描述

2.2 题解 

 2.3 代码实现

3. 二叉树剪枝

3.1 题目描述

3.2 题解 

3.3 代码实现 

4. 验证二叉搜索树 

4.1 题目描述 

 4.2 题解

4.3 代码实现 

 5.二叉搜索树中第k个小的元素

 5.1 题目描述

5.2 题解 

5.3 代码实现 

 6. 二叉树的所有路径

6.1 题目描述 

6.2 题解 

6.3 代码实现 

---

1. 计算布尔二叉树的值 

 1.1 题目描述

1.2 题解

1. 返回值：当前节点值；
2. 参数：当前节点指针。
3. 函数作⽤：求得当前节点通过逻辑运算符得出的值。

1. 当前问题规模为 n=1 时，即叶⼦节点，直接返回当前节点值；
2. 递归求得左右⼦节点的值；
3. 通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果；

1.3 代码实现 

    public boolean evaluateTree(TreeNode root) {
        //出口
        if(root.left == null) {
            return root.val == 0 ? false : true;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }

 2. 求根节点到叶子节点数字之和

 2.1 题目描述

2.2 题解 

1. 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递 归；
2.  当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。 在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

 2.3 代码实现

    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root,int preSum) {
        preSum = preSum * 10 + root.val;
        //递归出口
        if(root.left == null && root.right == null) {
            return preSum;
        }
        int num = 0;
        if(root.left != null) {
            num += dfs(root.left,preSum);
        }
        if(root.right != null) {
            num += dfs(root.right,preSum);
        }
        return num;
    }

3. 二叉树剪枝

3.1 题目描述

3.2 题解 

1. 返回值：⽆；
2. 参数 ：当前需要处理的节点；
3. 函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。

1. 递归出⼝：当传⼊节点为空时，不做任何处理；
2. 递归处理左⼦树；
3. 递归处理右⼦树；
4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点）， 并且节点的值为 0： a. 如果是，就删除掉； b. 如果不是，就不做任何处理。

3.3 代码实现 

    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) {
            root = null;
        }
        return root;
 
    }

4. 验证二叉搜索树 

4.1 题目描述 

 4.2 题解

4.3 代码实现 

    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        boolean left = isValidBST(root.left);
        //剪枝
        if(left == false) {
            return false;
        }
        //当前节点
        boolean ret = false;
        if(prev < root.val) {
            prev = root.val;
            ret = true;    
        }
        boolean right = isValidBST(root.right);
        return left && ret && right;
    }

 5.二叉搜索树中第k个小的元素

 5.1 题目描述

5.2 题解 

5.3 代码实现 

    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        count--;
        if(count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }

 6. 二叉树的所有路径

6.1 题目描述 

6.2 题解 

1. 如果当前节点不为空，就将当前节点的值加⼊路径 path 中，否则直接返回；
2. 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组 ret 中；
3. 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
4. 返回结果数组。

6.3 代码实现 

    List<String> ret;
 
    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root, new StringBuffer());
        return ret;
    }
 
    public void dfs(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if (root.left == null && root.right == null) {
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if (root.left != null) {
            dfs(root.left, path);
        }
        if (root.right != null)
            dfs(root.right, path);
    }