速通Hot100-Day09——二叉树

【递归思想三部曲】确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑144. 二叉树的前序遍历/** * 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 { ListInteger res new ArrayList(); public ListInteger preorderTraversal(TreeNode root) { if(root null) return res; preOrder(root); return res; } private void preOrder(TreeNode t) { if(t null) return; res.add(t.val); if(t.left ! null) preOrder(t.left); if(t.right ! null) preOrder(t.right); } }94. 二叉树的中序遍历/** * 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 { ListInteger res new ArrayList(); public ListInteger inorderTraversal(TreeNode root) { if(root null) return res; inOrder(root); return res; } private void inOrder(TreeNode t) { if(t null) return; if(t.left ! null) inOrder(t.left); res.add(t.val); if(t.right ! null) inOrder(t.right); } }145. 二叉树的后序遍历/** * 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 { ListInteger res new ArrayList(); public ListInteger postorderTraversal(TreeNode root) { if(root null) return res; postOrder(root); return res; } private void postOrder(TreeNode t) { if(t null) return; if(t.left ! null) postOrder(t.left); if(t.right ! null) postOrder(t.right); res.add(t.val); } }102. 二叉树的层序遍历时间复杂度O(n)其中 n 为二叉树的节点个数每个节点只会遍历一遍。空间复杂度O(n)。队列中元素不超过 n 个。只需要注意队列的实现以及使用即可。这个是手写队列。/** * 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 ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); TreeNode[] q new TreeNode[2010]; int hh 0,tt -1; if(root null) return res; q[tt] root; while(hh tt) { int len tt - hh 1; ListInteger tmp new ArrayList(); while(len -- 0) { TreeNode t q[hh]; tmp.add(t.val); if(t.left ! null) q[tt] t.left; if(t.right ! null) q[tt] t.right; } res.add(tmp); } 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 ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if(root null) return res; LinkedListTreeNode q new LinkedList(); q.offer(root); while(!q.isEmpty()) { int curSize q.size(); ListInteger tmp new ArrayList(); while(curSize -- 0) { TreeNode t q.poll(); tmp.add(t.val); if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); } res.add(tmp); } return res; } }226. 翻转二叉树交换指针而不是交换节点值。使用前序遍历对其左右子树直接交换即可。/** * 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 TreeNode invertTree(TreeNode root) { if(root null) return null; traversal(root); return root; } private void traversal(TreeNode cur) { if(cur null) return; TreeNode tmp new TreeNode(); tmp cur.left; cur.left cur.right; cur.right tmp; traversal(cur.left); traversal(cur.right); } }即使左右子树一个为空那也可以交换。所以这里层序遍历一层一层进行交换也是可以的/** * 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 TreeNode invertTree(TreeNode root) { if(root null) return null; LinkedListTreeNode q new LinkedList(); q.offer(root); while(!q.isEmpty()) { int curSize q.size(); while(curSize -- 0) { TreeNode t q.poll(); if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); TreeNode tmp t.left; t.left t.right; t.right tmp; } } return root; } }101. 对称二叉树为什么要后续遍历我们要去判断一棵树是否对称那么必然是要判断出该树的所有子树都是对称的这也就意味着最后再去判断根节点左 右 中。在compare逻辑中是一个父节点与其左右孩子节点的逻辑。无非都空、左空、右空、值不相等、相等的情况。如果是前4种情况可以直接判断结果最后一种结果就要去看其子节点就递归下去了先看子节点最后传导父节点判断结果。其实是比较两个子树是否可以翻转这个说法成立不成立。从理解上是这样但就是对称。要比较左右子树是否完全对称再去判断整棵树是否对称。/** * 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 isSymmetric(TreeNode root) { if(root null) return true; return traversal(root.left, root.right); } private boolean traversal(TreeNode left, TreeNode right) { if(left null right null) return true; if(left ! null right null) return false; if(left null right ! null) return false; if(left.val ! right.val) return false; boolean out traversal(left.left, right.right); boolean in traversal(left.right, right.left); return in out; } }104. 二叉树的最大深度就是求解一个树的高度问题求最高的子树的高度。/** * 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 maxDepth(TreeNode root) { if(root null) return 0; return getDepth(root); } 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; } }使用层序求解一共多少层就是最大深度。/** * 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 maxDepth(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(); if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); } res; // 一层节点一计算 } return res; } }111. 二叉树的最小深度同理就是求解一个树的高度问题求最高的子树的高度。那么这里认为null 子树不算计算另一个子树高度。为什么要这样计算null 节点不算是叶子节点所以计算的是叶子节点的深度。/** * 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 minDepth(TreeNode root) { if(root null) return 0; return getDepth(root); } private int getDepth(TreeNode cur) { if(cur null) return 0; int left getDepth(cur.left); int right getDepth(cur.right); if(cur.left null) return right 1; if(cur.right null) return left 1; return Math.min(left, right) 1; } }层序遍历求解不过特殊情况就是这一层结束了并且没有下一层了所以必须 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 minDepth(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(); if(t.left null t.right null) { res; return res; } if(t.left ! null) q.offer(t.left); if(t.right ! null) q.offer(t.right); } res; // 一层节点一计算 } return res; } }