面试最常见算法1—树—基础篇

时间：2023-02-16 19:08:22

前言

关于树的算法基本解法就三类：递归，队列，栈

刷题网站推荐：

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;
}

​​https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=13&tqId=11171&tab=answerKey&from=cyc_github​​

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);
}

​​https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github​​

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;
}

​​https://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff?tpId=13&tqId=2305268&ru=%2Fpractice%2F57aa0bab91884a10b5136ca2c087f8ff&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=​​

11.判断是不是平衡二叉树

private boolean isBalanced = true;

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);
}

​​https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github​​

标签：

相关文章