速通Hot100-Day10——二叉树

今天这种关于二叉树中判断是否是遍历当前节点的写法让我受学习。不过可能那种父亲角度理解的面试官喜欢吧。222. 完全二叉树的节点个数就是简单的递归求取节点有点类似于求取树的高度了/** * 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 int countNodes(TreeNode root) { if(root null) return 0; return getNode(root); } private int getNode(TreeNode cur) { if(cur null) return 0; int left getNode(cur.left); int right getNode(cur.right); return left right 1; } }110. 平衡二叉树平衡最后需要统一判断是否左右子树高度的差值。/** * 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 boolean isBalanced(TreeNode root) { if(root null) return true; return traversal(root); } private boolean traversal(TreeNode cur) { if(cur null) return true; boolean l traversal(cur.left); boolean r traversal(cur.right); int left getDepth(cur.left); int right getDepth(cur.right); int diff Math.abs(left - right); return l r diff 1; } private int getDepth(TreeNode cur) { if(cur null) return 0; int left getDepth(cur.left); int right getDepth(cur.right); return Math.max(left, right) 1; } }257. 二叉树的所有路径就是递归理解递归的条件、出口、参数即可。/** * 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 ListString binaryTreePaths(TreeNode root) { ListString paths new ArrayList(); if(root null) return paths; dfs(root, , paths); return paths; } private void dfs(TreeNode cur, String path, ListString paths) { if(path.isEmpty()) { path cur.val ; } else { path path - cur.val; } if(cur.left null cur.right null) { paths.add(path); return; } if(cur.left ! null) dfs(cur.left, path, paths); if(cur.right ! null) dfs(cur.right, path, paths); } }112. 路径总和这里存储两个队列到当前节点就计算当前的总和totalSum并非提前计算所以会清楚一点。那么要求一开始 sum 初始值 0如果想要提前计算那么sum 初始值是 root.val/** * 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 boolean hasPathSum(TreeNode root, int targetSum) { if(root null) return false; LinkedListTreeNode q new LinkedList(); q.offer(root); LinkedListInteger sum new LinkedList(); sum.offer(0); while(!q.isEmpty()) { int curSize q.size(); while(curSize -- 0) { TreeNode t q.poll(); int curSum sum.poll(); int totalSum curSum t.val; if(t.left null t.right null totalSum targetSum) return true; if(t.left ! null) { q.offer(t.left); sum.offer(totalSum); } if(t.right ! null) { q.offer(t.right); sum.offer(totalSum); } } } return false; } }404. 左叶子之和这个节点有点是站在父亲节点的角度去判断的是否是左节点然后是叶子节点。/** * 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 int sumOfLeftLeaves(TreeNode root) { if(root null) return 0; LinkedListTreeNode q new LinkedList(); q.offer(root); int res 0; while(!q.isEmpty()) { int curSize q.size(); for(int i 0;i curSize;i) { TreeNode t q.poll(); if(t.left ! null t.left.left null t.left.right null) res t.left.val; if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); } } return 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 int sumOfLeftLeaves(TreeNode root) { if(root null) return 0; LinkedListTreeNode q new LinkedList(); q.offer(root); LinkedListBoolean isLeft new LinkedList(); isLeft.offer(false); int res 0; while(!q.isEmpty()) { int curSize q.size(); for(int i 0;i curSize;i) { TreeNode t q.poll(); boolean flag isLeft.poll(); if(flag t.left null t.right null) res t.val; if(t.left ! null) { q.offer(t.left); isLeft.offer(true); } if(t.right ! null) { q.offer(t.right); isLeft.offer(false); } } } return res; } }513. 找树左下角的值这个层序先加入右节点再左节点那么最后一个元素必然是个左下角。所以只需要让 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 int findBottomLeftValue(TreeNode root) { if(root null) return 0; LinkedListTreeNode q new LinkedList(); q.offer(root); int res 0; while(!q.isEmpty()) { int curSize q.size(); while(curSize-- 0) { TreeNode t q.poll(); res t.val; if(t.right ! null) q.offer(t.right); if(t.left ! null) q.offer(t.left); } } return 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 int findBottomLeftValue(TreeNode root) { if(root null) return 0; LinkedListTreeNode q new LinkedList(); q.offer(root); int res 0; while(!q.isEmpty()) { int curSize q.size(); for(int i 0;i curSize;i){ TreeNode t q.poll(); if(i 0) res t.val; if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); } } return res; } }