二叉树中的深搜

一. 计算布尔二叉树的值

计算布尔二叉树的值

class Solution {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;}
}

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

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

class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int sum){if(root == null) return 0;int tmp = sum * 10 + root.val;if(root.left == null && root.right == null){return tmp;}return dfs(root.left, tmp) + dfs(root.right, tmp);}
}

三. 二叉树剪枝

二叉树剪枝

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

四. 验证二叉搜索树

验证二叉搜索树

class Solution {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 cur = false;if(root.val > prev) cur = true;//剪枝if(cur == false) return false;prev = root.val;//判断右子树是否是二叉搜索树boolean right = isValidBST(root.right);return left && cur && right;}
}

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

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

class Solution {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;//剪枝if (count == 0)return;dfs(root.left);count--;if (count == 0) {ret = root.val;//剪枝return;}dfs(root.right);}
}

六. 二叉树的所有路径

二叉树的所有路径

class Solution {List<String> ret = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {StringBuffer path = new StringBuffer();dfs(root, path);return ret;}public void dfs(TreeNode root, StringBuffer _path){//让每次递归修改的不是同一个path----'还原现场'StringBuffer path = new StringBuffer(_path);if(root == null) return ;path.append(Integer.toString(root.val));//如果是叶子结点if(root.left == null && root.right == null) {ret.add(path.toString());//结果加入到ret中return;}//不是叶子结点path.append("->");dfs(root.left, path);dfs(root.right, path);}
}