算法之：樹和二叉樹常見算法
2023-04-12
背景：在一些大公司，包括面試過程中，對一些常見的算法要求還是比較多的。書、二叉樹、紅黑樹，被問比較多的一些，接下來，我將整理一些常見的算法，以供大家參考。
第一題：遍歷二叉樹的高度
解釋：二叉樹是一種有規(guī)則的樹，所以在遍歷的時候，遞歸使用的比較多。(關(guān)于遞歸，不太了解的可以百度一下遞歸算法)
public class TreeNode {
public TreeNode left;
public TreeNode right;
int val;
}
public int getTreeMaxHeight(TreeeNode node) {
if(node==null)
return 0;
//遍歷左邊和右邊的子節(jié)點高度，求max，然后加上root(1)，
return 1+Math.max(getTreeMaxHeight(node.left),getTreeMaxHeight（node.righte）);
}第二題：二叉樹中的最大路徑和
public class TreeNode {
public TreeNode left;
public TreeNode right;
int val;
}
public class Solution {
int maxnum=0;
public static void main() {
Solution action=new Solution ();
action.DFS();
System.out.printf(maxnum);
}
//遍歷
public int DFS(TreeNode node)
{
if(node==null)
retrun 0;
int left=Math.max(node.left,0);
int right=Math.max(node.right,0);
maxnum=Math.max(maxnum,node.val+left+right);
return node.val+Math.max(left,right);
}第三題：求某個節(jié)點以雙親子節(jié)點的最大和。(滿樹)
int max=0;
public int dfs(TreeNode node) {
if(node==null) {
return 0;
}
if(node.left!=null&&node.right!=null)
{
int sum=node.val+node.left.val+node.right.val;
max= Math.max(max,sum);
}
dfs(node.left);
dfs(node.right);
return 0;
}第三題：二叉樹的遍歷
1.采用遞歸方式
前序、后序、中序遍歷，只是輸出位置不同
public void dfs(Tree tree)
{
if(tree==null)
return;
system.out.printf(tree.val);//前序遍歷的結(jié)果
dfs(tree.left)
system.out.printf(tree.val);//中序遍歷的結(jié)果
dfs(tree.right);
system.out.printf(tree.val);//后序遍歷的結(jié)果
}2.前序遍歷：非遞歸
public void logTreeFront(TreeNode root) {
Stack stack = new Stack<>();//用一個棧來存放樹中的節(jié)點
while (root != null || !stack.isEmpty()) {
訪問完畢)或者棧中還有節(jié)點(還有節(jié)點沒有訪問)
while (root != null) {//一直往左走
stack.push(root);//根節(jié)點入棧
System.out.println(root.val);//前序點
root = root.left;//訪問左子樹
}
root = stack.pop();//取出根節(jié)點
root = root.right;//訪問右子樹
}
}
3.中序遍歷：非遞歸
public void logTreeCenter(TreeNode root){
Stack stack = new Stack<>();
while(root != null || !stack.isEmpty()){//只要當(dāng)前節(jié)點不為空(即當(dāng)前節(jié)點的左右子樹沒有訪 問完畢)或者棧中還有節(jié)點(還有節(jié)點沒有訪問)
while(root != null){
stack.push(root);//根節(jié)點入棧
root = root.left;//訪問左子樹
}
root = stack.pop();//取出左子樹的根節(jié)點
System.out.println(root.val);//輸出中序
root = root.right;//訪問右子樹
}
}
4.后序遍歷：非遞歸
private void endLogTree(TreeNode tree) {
if (tree == null)
return;
Stack stack = new Stack();
TreeNode node = tree;
TreeNode prev = null;
while (node!=null||!stack.isEmpty()) {
//處理左子樹
while (node != null) {
stack.push(node);
//這邊繼續(xù)遍歷
node = node.left;
}
node = stack.peek();
//處理右子樹
if (node.right == null || node.right == prev) {
//將頂部的出棧
stack.pop();
//打印節(jié)點
System.out.println(node.val);
prev = node;//下一個節(jié)點指向
node = null;//當(dāng)前節(jié)點遍歷完，需要釋放
} else {
node = node.right;
}
}
}
第四題：創(chuàng)建二叉樹,完整樹
public TreeNode createTree(int[] objs) {
List datas = new ArrayList();
for (Integer object : objs) {
datas.add(new TreeNode(object));
}
TreeNode root = datas.get(0);//將第一個作為根節(jié)點
for (int i = 0; i < objs.length / 2; i++) {
//樹是對稱圖像，只需要計算左邊
//左子樹的位置2*1+1
datas.get(i).left = datas.get(i * 2 + 1);
//右子樹:i*2+2
if (i * 2 + 2 < datas.size()) {
datas.get(i).right = datas.get(i * 2 + 2);
}
}
return root;
}
第五題：二叉樹的層遍歷
public void logLevel(TreeNode treeNode) {
if (treeNode == null)
return;
Queue queue = new LinkedList<>();//層序遍歷時保存結(jié)點的隊列
queue.offer(treeNode);//初始化
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.print(node.val + " ");//訪問節(jié)點
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
}
備注：關(guān)于Queue的add和offer,一個會引起異常，一個不會。所以不了解隊列的，可以自己看下API。
本文僅代表作者觀點，版權(quán)歸原創(chuàng)者所有，如需轉(zhuǎn)載請在文中注明來源及作者名字。
免責(zé)聲明：本文系轉(zhuǎn)載編輯文章，僅作分享之用。如分享內(nèi)容、圖片侵犯到您的版權(quán)或非授權(quán)發(fā)布，請及時與我們聯(lián)系進(jìn)行審核處理或刪除，您可以發(fā)送材料至郵箱：service@tojoy.com