二叉树的深搜

前言： 本章节更深入学习递归

计算布尔二叉树的值

 

思路： 
1.函数头设计：dfs（root）

2.函数体：需要一个接收left 和 right 的值  并且根据root的值进行比较

3.递归出口：很明显 当为叶子节点的时候 向上返回你叶子节点的值 并且与当前root的值进行比较

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

---

求根节点到叶节点数字之和

 

从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

    int ret = 0;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 ret += preSum;}if (root.left != null) {dfs(root.left, preSum);}if (root.right != null) {dfs(root.right, preSum);}return ret;}

---

 二叉树剪枝

 

思路： 叶子节点为0 直接让它指向空  后序遍历思想

1.遍历完左子树 再遍历右子树

2. 如果遇到叶子节点 则判断当前节点是否为0 

3.如果为0 则直接返回null  否则不需要剪枝 直接返回原来值

    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) {return null;} else {return root;}}

---

验证二叉搜索树

思路：二叉搜索树 中序遍历是一个有序数组 利用这一特性
先定义一个最小数字prev

当遍历完左子树回退时候

比较是否prev跟当前回退的数字大小 

如果比prev大 则让prev=当前节点的值 

否则 就不是二叉搜索树

    long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left) || root.val <= prev) {return false;}prev = root.val;return isValidBST(root.right);}

---

 二叉搜索树中第 K 小的元素

 思路： 要求二叉搜索树第k大的数字

定义俩个全局变量 ret记录最终结果 count记录当前k

依次遍历到左子树 当为空的时候 就该回退了

并且 count-1 当count为0的时候 就是目标值了

 int ret;int count ;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);}