二叉树
完全二叉树的节点个数
给定一个完全二叉树，求节点个数。
完全二叉树从数组的形式上看就是中间没有空节点 root = [1,2,3,4,5,6]
首先想到的自然是层序遍历，完全二叉树的结构和层序遍历太契合了，一旦我们发现空节点立刻就能返回。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
LinkedList<TreeNode> list = new LinkedList<>();
list.offer(root);
int n = 1;
while(!list.isEmpty()) {
TreeNode node = list.poll();
if(node.left == null) {
return n;
}
list.offer(node.left);
n++;
if(node.right == null) {
return n;
}
list.offer(node.right);
n++;
}
return n;
}
}
|
耗时稍微多了些，毕竟节点需要在队列里进进出出。
想想能不能改进一下，注意到其实队列中的头节点完全没必要出队列，保留所有节点甚至还不需要变量充当计数器了，直接返回队列的长度即可，LinkedList也换成ArrayList数组实现，因为我们保留了一些所有节点如何用链表的话获取节点会较为缓慢（原来是只需要取出队首的节点就行）。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
ArrayList<TreeNode> list = new ArrayList<>();
list.add(root);
int n = 0;
while(true) {
TreeNode node = list.get(n++);
if(node.left == null) {
return list.size();
}
list.add(node.left);
if(node.right == null) {
return list.size();
}
list.add(node.right);
}
}
}
|
那么再尝试用递归做一下。
class Solution {
int n = 0;
public int countNodes(TreeNode root) {
if(root == null) {
return n;
}
n++;
countNodes(root.left);
countNodes(root.right);
return n;
}
}
|
递归的代码还是一如既往的简洁优雅，用时也是最短的。
毕竟迭代的话需要对额外的数据结构维护和操作，这通常比函数调用的时间开销大。如果把前面几道题的递归和迭代的两种方法的用时进行比较，大部分情况下也是递归的用时更少（不过时间复杂度上二者一般是一个量级的）。
看解析看到一种更优的解法
class Solution {
int n = 0;
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
TreeNode node = root;
int left = 1;
while(node.left != null) {
node = node.left;
left++;
}
int right = 1;
while(node.right != null) {
node = node.right;
right++;
}
if(left == right) {
return (int)Math.pow(2, left) -1;
}
int leftNodes = countNodes(root.left);
int rightNodes = countNodes(root.right);
return leftNodes + rightNodes + 1;
}
}
|
之前的方法没有将“完全二叉树”这个条件利用到极致。对于完全二叉树来说，只要一直往左的深度等于一直往右的深度，那么这个完全二叉树就是满二叉树，而对于非满二叉树的完全二叉树来说，有一个神奇的特性，即使它自己不是满二叉树，它往下分支到一定程度后，其节点的左子树和右子树必然为满二叉树（或者空树），而且对于任一节点来说，如果只要其中一个子树不为满二叉树，那么其另一子树必然为满二叉树，那么就可以用递归实现这种奇妙的算法。
这种算法的时间复杂度居然只有O(log n)~O(log n * log n)，最好情况是整棵树为满二叉树，左右各探查一遍就可以公式算出结果，时间复杂度为O(log n)，最坏情况是一直发现其中一个子树不为满二叉树（由于完全二叉树两棵子树中至少有一棵满二叉树的特性），那么探查次数为O(log n)级，每次探查也是O(log n)级，总的时间复杂度就是O(log n * log n)级别
更牛的是它的空间复杂度也只有O(log n)级别，无敌了。
平衡二叉树
给定一个二叉树，判断它是否是高度平衡二叉树。
高度平衡二叉树：任意节点的左右子树的高度差距不超过1。
先用递归试试。
class Solution {
boolean balance = true;
public boolean isBalanced(TreeNode root) {
howDeep(root);
return balance;
}
public int howDeep(TreeNode root) {
if(root == null) {
return 0;
}
int left = howDeep(root.left);
int right = howDeep(root.right);
if(Math.abs(left - right) > 1) {
balance = false;
}
return Math.max(left, right) + 1;
}
}
|
二叉树的深度是由上到下，高度是由下到上。
首先高度和深度是不一样的概念，但是一棵树的最大高度和最大深度是相等的，所以可以利用这一关系。而递归求出高度的时候是由下而上的（某节点的高度等于其子树高度较大值加一），那为了顺着递归的顺序，最好的方式就是在求高度的过程中顺便比较小子树是否平衡是最恰当的。按照这个思路实现就是以上代码。写代码的过程中可能遇到一个问题，那就是函数是只有一个返回值的，而上层节点的高度是由下层节点求得，需要返回高度值，那么这个过程中要如何判断子树是否平衡呢，那么可以采取设置一个实例变量（类变量）的方式，在方法中修改它的值。
那么我再尝试一下迭代。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
Stack<TreeNode> st = new Stack<>();
st.push(root);
HashMap<TreeNode, Integer> map = new HashMap<>();
while(!st.isEmpty()) {
TreeNode node = st.pop();
boolean leftSeeked = node.left == null || map.containsKey(node.left);
boolean rightSeeked = node.right == null || map.containsKey(node.right);
if(leftSeeked && rightSeeked) {
int left = node.left == null? 0:map.get(node.left);
int right = node.right == null? 0:map.get(node.right);
if(Math.abs(left-right) > 1) {
return false;
}
map.put(node, Math.max(left, right) + 1);
continue;
}
st.push(node);
if(node.right != null) {
st.push(node.right);
}
if(node.left != null) {
st.push(node.left);
}
}
return true;
}
}
|
这道题用迭代还真有点伤脑经，因为我们需要知道什么时候应该判断某节点是否平衡，我一开始想的是通过节点的val字段存储节点的高度，但是因为val本身就有值，无法判断该节点的val是否已经替换为子树的高度，或者我可以采取先将所有节点的值初始化为-1，以此进行判断，不过初始化的过程需要先遍历一遍树，于是我就干脆使用一个map来存储节点对应的子树高度好了，对于map的用法还需熟练。
下面是初始化为-1的代码，原理是一样的。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
Stack<TreeNode> st = new Stack<>();
st.push(root);
initVal(root);
while(!st.isEmpty()) {
TreeNode node = st.pop();
boolean leftSeeked = node.left == null || node.left.val != -1;
boolean rightSeeked = node.right == null || node.right.val != -1;
if(leftSeeked && rightSeeked) {
int left = node.left == null? 0:node.left.val;
int right = node.right == null? 0:node.right.val;
if(Math.abs(left-right) > 1) {
return false;
}
node.val = Math.max(left, right) + 1;
continue;
}
st.push(node);
if(node.right != null) {
st.push(node.right);
}
if(node.left != null) {
st.push(node.left);
}
}
return true;
}
public void initVal(TreeNode node) {
if(node == null) {
return;
}
node.val = -1;
initVal(node.left);
initVal(node.right);
}
}
|
二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径
第一反应肯定是递归。
class Solution {
List<String> paths = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
binaryTreePath(root, "");
return paths;
}
public void binaryTreePath(TreeNode node, String prePath) {
String s = String.valueOf(node.val);
if(prePath.isEmpty()) {
prePath = s;
} else {
prePath = prePath + "->" + s;
}
if(node.left == null && node.right == null) {
paths.add(prePath);
return;
}
if(node.left != null) {
binaryTreePath(node.left, prePath);
}
if(node.right != null) {
binaryTreePath(node.right, prePath);
}
}
}
|
用时比较长，难道是字符串拼接导致的。尝试把路径所经过的节点存在一个数组中，最后输出结果就在中间插入”->”，这是初步想法。
稍微修改一下代码，这里就加上了回溯的思路，不过上面第一种方法也可以说有回溯，当我们进入下一层递归时传入的参数是prePath，prePath在下一层递归中才进行加工，不会影响上一层的prePath，相当于做了一个标记用来回档了，也可以认为是一种回溯吧。
class Solution {
List<String> paths = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
binaryTreePath(root, new ArrayList<String>());
return paths;
}
public void binaryTreePath(TreeNode node, List<String> prePath) {
prePath.add(String.valueOf(node.val));
if(node.left == null && node.right == null) {
paths.add(String.join("->", prePath));
return;
}
if(node.left != null) {
binaryTreePath(node.left, prePath);
prePath.removeLast();
}
if(node.right != null) {
binaryTreePath(node.right, prePath);
prePath.removeLast();
}
}
}
|
还有什么更优的解法吗，看解析将ArrayList换成效率更高的StringBuilder试试。
class Solution {
List<String> paths = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root == null) {
return paths;
}
binaryTreePath(root, new StringBuilder());
return paths;
}
public void binaryTreePath(TreeNode node, StringBuilder prePath) {
int length = prePath.length();
if(prePath.isEmpty()) {
prePath.append(String.valueOf(node.val));
} else {
prePath.append("->" + String.valueOf(node.val));
}
if(node.left == null && node.right == null) {
paths.add(prePath.toString());
}
if(node.left != null) {
binaryTreePath(node.left, prePath);
}
if(node.right != null) {
binaryTreePath(node.right, prePath);
}
prePath.setLength(length);
}
}
|
注意这里回溯用到了一个技巧，prePath.setLength(length);直接截断。
似乎还有改进空间，用时上。
class Solution {
List<String> paths = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root == null) {
return paths;
}
binaryTreePath(root, new StringBuilder());
return paths;
}
public void binaryTreePath(TreeNode node, StringBuilder prePath) {
int length = prePath.length();
if(prePath.isEmpty()) {
prePath.append(String.valueOf(node.val));
} else {
prePath.append("->").append(String.valueOf(node.val));
}
if(node.left == null && node.right == null) {
paths.add(prePath.toString());
}
if(node.left != null) {
binaryTreePath(node.left, prePath);
}
if(node.right != null) {
binaryTreePath(node.right, prePath);
}
prePath.setLength(length);
}
}
|
prePath.append("->").append(String.valueOf(node.val));因为之前的方式prePath.append("->" + String.valueOf(node.val));需要生成一个中间字符串，会稍微增加用时。
在写算法题的过程中注意提高阅读他人代码的能力，还可以注意每种算法的时间复杂度和空间复杂度
我们这里使用的paths是实例变量（作用域是整个类），在写算法题的过程中写这种写法倒是问题不大，还可以让代码更简洁，但是在实际工程中最好不要写成这种形式，最好采取局部变量的方式，把参数放到方法内。至于为什么，使用实例变量的话，一是方法中会隐式地用到paths这个变量，但是这在方法签名中并没有体现（方法的传入参数并没有这个变量），二是线程安全问题，当多个线程同时调用binaryTreePath，共享的paths可能出现数据竞争，三是结果会累加，当我们多次调用binaryTreePath时，paths中的结果会累加（需要额外进行重置操作），这几点原因可能会在工程中导致问题，所以在写工程代码时最好采用局部变量这种方式，代码附下。
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if(root == null) {
return paths;
}
binaryTreePath(root, new StringBuilder(), paths);
return paths;
}
public void binaryTreePath(TreeNode node, StringBuilder prePath, List<String> paths) {
int length = prePath.length();
if(prePath.isEmpty()) {
prePath.append(String.valueOf(node.val));
} else {
prePath.append("->").append(String.valueOf(node.val));
}
if(node.left == null && node.right == null) {
paths.add(prePath.toString());
}
if(node.left != null) {
binaryTreePath(node.left, prePath, paths);
}
if(node.right != null) {
binaryTreePath(node.right, prePath, paths);
}
prePath.setLength(length);
}
}
|
参考链接：
【代码随想录】https://www.programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
