Leetcode二叉树部分笔记

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

1.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

**解题思路：**如果用广度优先遍历的话，设置一个队列，quque.offer代表让节点进入队列，判断当前队列内还有没有值，如果有则把它的左右孩子放进来，并把size–，每清空一次队列，代表遍历了一层，建一个计数器每遍历一层，计数器加一。最终得到深度。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;}
}

**解题思路2：**使用深度优先遍历，采用递归：假设深度优先到最后一层，执行这个函数，左孩子为null，右孩子为null，左孩子执行这个函数，返回0，右孩子执行这个函数，也返回0。该节点返回1，它的上一层 leftHeight就成1了。同理，如果他的上一层没有右孩子，则右孩子返回0，则这个上一层返回2。以此类推。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

2.同样的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**解题思路：**使用深度优先遍历。假设p和q都到了最后一层，p,left == null，q.left ==null,因此函数返回true，同理p.right == null 并且q.right == null，同样返回true，这样该节点返回一个true，返回给上一层，看看第一层是不是都是true。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null && q==null){return true;}else if(p==null || q==null){return false;}else if(p.val != q.val){return false;}else{return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}
}

3.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解题思路：假设在最后一层的两个节点，这两个节点的四个孩子都是null，返回他们本身就可以，这两个节点的上一层的父节点，接收到下面返回上来的left和right，并对这两个进行置换，把它自身返回上去，以此类推。

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}

4.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

**解题思路：**也就是判断L.left和R.right 以及 L.right = R.left，是否都能同时到达最底部，如果没有则说明不对称。

class Solution {public boolean isSymmetric(TreeNode root) {return root == null || recur(root.left, root.right);}boolean recur(TreeNode L, TreeNode R) {if (L == null && R == null) return true;if (L == null || R == null || L.val != R.val) return false;return recur(L.left, R.right) && recur(L.right, R.left);}
}作者：Krahets
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

**5. 填充每个节点的下一个右侧节点指针 II

给定一个二叉树：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

**解题思路：**层序遍历，设置一个指针，如果当前层的大小不为1，则说明后面还有，让这个指针的next指向poll出来的节点，再让指针更新，如果大小为1，则不做任何操作。

class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();Node last = null;for (int i = 1; i <= n; ++i) {Node f = queue.poll();if (f.left != null) {queue.offer(f.left);}if (f.right != null) {queue.offer(f.right);}if (i != 1) {last.next = f;}last = f;}}return root;}
}

6. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

**解题思路:**设置一个pre，专门寻找root节点的left孩子的最右侧孩子，到达最右侧后让最右侧的右指针指向root的右孩子，让root的右指针指向root的左孩子，再让root向下走，遍历一遍。

class Solution {public void flatten(TreeNode root) {while (root != null) { //左子树为 null，直接考虑下一个节点if (root.left == null) {root = root.right;} else {// 找左子树最右边的节点TreeNode pre = root.left;while (pre.right != null) {pre = pre.right;} //将原来的右子树接到左子树的最右边节点pre.right = root.right;// 将左子树插入到右子树的地方root.right = root.left;root.left = null;// 考虑下一个节点root = root.right;}}
}

7. 路经总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

**解题思路：**假设在最后一层，发现root.left == null && root.right ==null 则返回当前value和sum值是否相等的判断，如果相等，则说明成立，直接返回true，如果不相等则返回false。

class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

8.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

class Solution {public int countNodes(TreeNode root) {if(root == null) {return 0;}int left = countNodes(root.left);int right = countNodes(root.right);return left+right+1;}
}