1. 2331. 计算布尔二叉树的值

 

1、宏观

        给定一个根节点，在进行运算结果前首先要知道该根节点左子树的整体结果和右子树的整体结果才能进行运算。

2、细节dfs

        从上往下遍历，从下往上计算，遍历停止开始算的结果是遍历到叶子结点。 

java">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;}
}

1. 2.129. 求根节点到叶节点数字之和

1、到5的时候首先要将12传入；

2、其次将12变成125，传入到左子树8和右子树9；

3、8和9返回他们作为根节点被其子树返回的数之和；

4、5节点将自己的子树和返回给自己的上级； 

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

814. 二叉树剪枝

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

  验证二叉搜索树

 

 解题性质：二叉搜索树中序遍历的结果，是一个有序的序列。设置全局变量prev=-无穷；

法一：左子树是二叉搜索树，右子树也是二叉搜索树，当前根节点所在的树也是二叉搜索树。

java">class Solution {long p =  Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null){return true;}boolean left = isValidBST(root.left);boolean cur = false;if(root.val > p){cur = true;}p = root.val;boolean right =isValidBST(root.right);return left && right && cur;}
}

法二：减枝

java">class Solution {long p =  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 > p){cur = true;}if(cur ==false){return false;}p = root.val;boolean right =isValidBST(root.right);return left && right && cur;}
}

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

 

中序遍历+两个全局变量 

 

java">class Solution {int count ;//计数int ret;//存值public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}void dfs(TreeNode root){if(root == null || count == 0){return;}dfs(root.left);count--;if(count == 0){ret = root.val;return;}dfs(root.right);}
}

1. 257. 二叉树的所有路径

 

java">/*** 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 {List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root,new StringBuffer());return ret;}void dfs(TreeNode root,StringBuffer path1){StringBuffer path = new StringBuffer(path1);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);}}
}

ps:谢谢观看。