前言
关于树的算法基本解法就三类：递归，队列，栈
刷题网站推荐：
- 牛客网
- Leetcode
1.二叉树遍历(前序)
public List<Integer> preorderTraversal(TreeNode root) {
// 1.递归实现
/**
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
*/
// 2.使用栈实现
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
TreeNode head = root;
Stack<TreeNode> stack = new Stack<>();
while (null != head || !stack.isEmpty()) {
if (null != head) {
res.add(head.val);
stack.push(head);
head = head.left;
} else {
head = stack.pop().right;
}
}
return res;
}前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/
中序遍历 https://leetcode.cn/problems/binary-tree-inorder-traversal/
后序遍历 https://leetcode.cn/problems/binary-tree-postorder-traversal/
2.二叉树层次遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int len = queue.size();
List<Integer> item = new ArrayList<>();
while(len > 0){
//从队列中取出数据
TreeNode node = queue.poll();
item.add(node.val);
//边读边取
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
len--;
}
res.add(item);
}
return res;
}https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/
其余的Z形打印或者锯齿打印都是它的变种
3.二叉树深度
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
else {
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return left > right ? left + 1 : right + 1;
}
}https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/
4.二叉树宽度
使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。
public int widthOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
Queue queue = new ArrayDeque();
int maxwitdth = 1; // 最大宽度
queue.add(root); // 入队
while (true) {
int len = queue.size(); // 当前层的节点个数
if (len == 0)
break;
while (len > 0) {// 如果当前层，还有节点
TreeNode t = (TreeNode) queue.poll();
len--;
if (t.left != null)
queue.add(t.left); // 下一层节点入队
if (t.right != null)
queue.add(t.right);// 下一层节点入队
}
maxwitdth = maxwitdth > queue.size() ? maxwitdth : queue.size();
}
return maxwitdth;
}5.判断一棵树是否为另一棵树的子树
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null || subRoot == null) {
return false;
}
return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSameTree(TreeNode s, TreeNode t) {
if (t == null && s == null) {
return true;
}
if (s == null || t == null) {
return false;
}
return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}https://leetcode.cn/problems/subtree-of-another-tree/submissions/
6.二叉树的右视图
public List<Integer> rightSideView(TreeNode root) {
int cnt=0,tmp=0;
TreeNode node;
List<Integer> res = new LinkedList<>();
if(root==null){
return res;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
cnt=queue.size();
while(cnt>0){
node=queue.poll();
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
cnt--;
tmp=node.val;
}
res.add(tmp);
}
return res;
}https://leetcode.cn/problems/binary-tree-right-side-view/submissions/
7.给定n求二叉搜索树的个数
class Solution {
public int numTrees(int n) {
//初始化 dp 数组
int[] dp = new int[n + 1];
//初始化0个节点和1个节点的情况
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
//对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
//一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}https://leetcode.cn/problems/unique-binary-search-trees/
8.二叉树的镜像
public TreeNode Mirror(TreeNode root) {
if (root == null)
return root;
swap(root);
Mirror(root.left);
Mirror(root.right);
return root;
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}9.对称的二叉树
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return true;
if (t1 == null || t2 == null)
return false;
if (t1.val != t2.val)
return false;
return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}10.二叉搜索树的第K个节点
由于是二叉搜索树，采用中序遍历得到的第k个节点即第k小的值，判断输出是否是第k个就可以返回值了，使用栈来辅助遍历
public int KthNode (TreeNode proot, int k) {
if (proot == null) return -1;
//中序遍历，第k个节点
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(proot);
TreeNode node = proot;
int i = 0;
while (!stack.isEmpty()) {
//遍历node下的所有左节点
while (node.left != null) {
stack.push(node.left);
node = node.left;
}
i++;
if (i == k) return stack.pop().val;
TreeNode tmp = stack.pop();
//加入右子树
if (tmp.right != null) {
stack.push(tmp.right);
node = tmp.right;
}
}
return -1;
}11.判断是不是平衡二叉树
private boolean isBalanced = true;标签：right,return,常见,面试,算法,TreeNode,null,root,left From： https://blog.51cto.com/u_13222507/6061711
public boolean IsBalanced_Solution(TreeNode root) {
getHeight(root);
return isBalanced;
}
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int left = getHeight(root.left);
int right = getHeight(root.right);
if(Math.abs(left - right) > 1) {
isBalanced = false;
}
return 1 + Math.max(left, right);
}