2020-07-11【树】
2020-07-11 本文已影响0人
桢桢claire
等待那一束光
今日鸡汤：
大脑的一切疲劳和压力来自于过去和未来：对已经发生的事情心有不甘，对将要发生的事情充满不安。
愿你内心平和，踏踏实实活在当下，不去悔恨过去，不去忧心未来。
今天一起来看树啦，多刷题，多刷题，有助于预防老年痴呆。
树的基础
1. 树的最大深度
最大深度一定是到叶子节点了才能判断是不是最深，为了记录层数，可以在遍历树的时候定义新的数据结构，另外存下来当前节点的层信息，这样访问叶子节点时，只要取出来判断一下就可以了。
class NodeLevel{
TreeNode node;
int level;
NodeLevel(TreeNode node,int level){
this.node = node;
this.level = level;
}
};
/**
*
* @param root TreeNode类
* @return int整型
*/
public int maxDepth (TreeNode root) {
// write code here
if(root == null) return 0;
return maxTreeDepth(root);
}
public int maxTreeDepth(TreeNode root){
int maxDepthVal = 0;
Stack<NodeLevel> parentStack = new Stack<NodeLevel>();
Stack<NodeLevel> childrenStack = new Stack<NodeLevel>();
// Add root to childrend stack
childrenStack.push(new NodeLevel(root, 1));
while(childrenStack.size() > 0){
// Get current top node.
NodeLevel topNode = childrenStack.pop();
int currentLevel = topNode.level;
if(topNode.node.right == null && topNode.node.left == null){
if(currentLevel > maxDepthVal) maxDepthVal = currentLevel;
} else{
// Add child nodes.
if(topNode.node.left != null){
childrenStack.add(new NodeLevel(topNode.node.left, currentLevel + 1));
}
if(topNode.node.right != null){
childrenStack.add(new NodeLevel(topNode.node.right, currentLevel + 1));
}
}
parentStack.push(topNode);
}
return maxDepthVal;
}
树的遍历
先来看树的遍历。主要分为前序（先序）、中序和后序，遍历方法也很直接，递归和非递归，递归比较简单，主要看一下非递归方式，涉及到不同的数据结构。
1. 前序遍历
前序遍历是按照<根、左、右>的方式来遍历，特点是根先出，所以可以用一个栈+一个队列的数据结构。栈用来存当前节点，队列用来按顺序存放遍历结果。注意压栈是要先右再左，这样出栈时才是先左后右。
public ArrayList<Integer> preorderTraversal (TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> preOrderList = new ArrayList<Integer>();
if(root == null) return preOrderList;
// Add root to stack
stack.push(root);
while(stack.size() != 0){
// Get top node and put it into list.
TreeNode topNode = stack.pop();
preOrderList.add(topNode.val);
// Push right node and left node to stack.
if(topNode.right != null){
stack.push(topNode.right);
}
if(topNode.left != null){
stack.push(topNode.left);
}
}
return preOrderList;
}
2. 中序遍历
中序遍历是按照<左、中、右>的方式遍历，特点是根在中间，可以根据根节点位置直接区分左右子树的元素。因此，可以用一个栈，直接DFS，一直找左节点，为空时出栈，再加入右节点。
public ArrayList<Integer> inorderTraversal (TreeNode root) {
ArrayList<Integer> traversalList = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode currentNode = root;
// When all nodes are processed, stack will be empty, stop the loop.
while(currentNode != null || !stack.isEmpty()){
if(currentNode != null){
// Push left node to the stack
stack.push(currentNode);
currentNode = currentNode.left;
} else{
// Pop current node in the stack
TreeNode popedNode = stack.pop();
// Add value to list
traversalList.add(popedNode.val);
// Push right node
currentNode = popedNode.right;
}
}
return traversalList;
}
3. 后序遍历
后序遍历是按照<左、右、中>的方式遍历，特点是根节点在最后，因此用两个栈，一个存放当前节点，一个存放当前节点的左右孩子。注意压栈时先左后右。
public ArrayList<Integer> postorderTraversal (TreeNode root) {
// write code here
ArrayList<Integer> postorderList = new ArrayList<Integer>();
if(root == null) return postorderList;
Stack<TreeNode> parentStack = new Stack<TreeNode>();
Stack<TreeNode> childrenStack = new Stack<TreeNode>();
// Put root into children stack.
childrenStack.push(root);
while(childrenStack.size() != 0){
// Pop top node and push it into parent stack.
TreeNode topNode = childrenStack.pop();
parentStack.push(topNode);
// Push left and right node into children stack.
if(topNode.left != null){
childrenStack.push(topNode.left);
}
if(topNode.right != null){
childrenStack.push(topNode.right);
}
}
// Pop element in parent stack and save it into list.
while(parentStack.size() != 0){
postorderList.add(parentStack.pop().val);
}
return postorderList;
}
4. 层次遍历（分层存储）
层次遍历是一层一层的从左往右遍历，遇到空节点直接跳过，所以可以用两个队列，一个队列放该层的节点，一个队列放上个队列所有节点的孩子，再倒手。
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> orderTraverseList = new ArrayList<ArrayList<Integer>>();
if(root == null) return orderTraverseList;
ArrayList<TreeNode> parentList = new ArrayList<TreeNode>();
parentList.add(root);
while(parentList != null && parentList.size() != 0){
// Add parent node list
orderTraverseList.add(generateVal(parentList));
// Generate children node list
ArrayList<TreeNode> childrenList = generateChildren(parentList);
//orderTraverseList.add(generateVal(childrenList));
parentList = childrenList;
}
return orderTraverseList;
}
public ArrayList<Integer> generateVal(ArrayList<TreeNode> nodeList){
ArrayList<Integer> valList = new ArrayList<Integer>();
for(TreeNode node: nodeList){
valList.add(node.val);
}
return valList;
}
public ArrayList<TreeNode> generateChildren(ArrayList<TreeNode> parentList){
ArrayList<TreeNode> childrenList = new ArrayList<TreeNode>();
// Pop nodes in list and save them to current level list.
for(TreeNode node: parentList){
// Save all children of nodes in queue1 to queue2
if(node.left != null){
childrenList.add(node.left);
}
if(node.right != null){
childrenList.add(node.right);
}
}
return childrenList;
}
各种奇葩的🌲
1. 判断是不是平衡二叉树
平衡二叉树就是每个节点左右子树高度差绝对值不超过1的二叉树，因此先递归计算左右子树的高度，再判断当前节点左右子树高度差是否满足条件，若满足，再对左右子树的结果做与运算即可。
public boolean isBalanced (TreeNode root) {
// write code here
if(root == null) return true;
int leftTreeHeight = getHeight(root.left);
int rightTreeHeight = getHeight(root.right);
if(Math.abs(leftTreeHeight - rightTreeHeight) <= 1){
return isBalanced(root.left) && isBalanced(root.right);
}
return false;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int left = getHeight(root.left) + 1;
int right = getHeight(root.right) + 1;
return (left > right) ? left: right;
}
