二叉樹的類由節(jié)點(diǎn)值左子樹和右子樹組成二叉樹的基本方法-四種遍歷1.先序遍歷 - 根左右 - ABDEHCFG 先序遍歷的第一個(gè)節(jié)點(diǎn)一定是根結(jié)點(diǎn)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)2.中序遍歷 - 左根右 - DBEHAFCG 中序遍歷根節(jié)點(diǎn)左邊全是左子樹中序遍歷的結(jié)果根節(jié)點(diǎn)的右邊一定是右子樹中序遍歷的結(jié)果3.后序遍歷 - 左右根 - DHEBFGCA 后序遍歷的最后一個(gè)節(jié)點(diǎn)一定是根節(jié)點(diǎn)4.層序遍歷 -二叉樹遍歷的還原后序先序 不能還原1.后序中序1先找出后序遍歷的最后一個(gè)節(jié)點(diǎn)該節(jié)點(diǎn)是根節(jié)點(diǎn)A2再把根節(jié)點(diǎn)對(duì)應(yīng)到中序遍歷結(jié)果中 根節(jié)點(diǎn)左邊的就是左子樹中序遍歷的結(jié)果DBEH根節(jié)點(diǎn)右邊的就是右子樹中序遍歷的結(jié)果FCG3把左子樹DBEH對(duì)應(yīng)到后序遍歷中去左子樹的后序遍歷就是DHEB,中序右子樹FCG對(duì)應(yīng)的后序右子樹遍歷就是FGC再依次類推B就是左子樹的根節(jié)點(diǎn)C就是右子樹的根節(jié)點(diǎn)2.先序中序1先找出先序遍歷的最前面的一個(gè)節(jié)點(diǎn)就收根節(jié)點(diǎn)A,2) 再把根節(jié)點(diǎn)A對(duì)應(yīng)的中序遍歷的結(jié)果中根節(jié)點(diǎn)A左邊就是左子樹中序遍歷的結(jié)果根節(jié)點(diǎn)右邊就是右子樹中序遍歷的結(jié)果3再把中序遍歷的左右子樹在先序遍歷結(jié)果里對(duì)應(yīng)BDEH就是左子樹先序遍歷的CFG就是右子樹先序遍歷的在以此類推B就是左子樹的根節(jié)點(diǎn)C就是右子樹的根節(jié)點(diǎn)總結(jié)后序/先序 中序 可以還原出原始的二叉樹1根據(jù)后序遍歷/先序結(jié)果找到根節(jié)點(diǎn)2根據(jù)根節(jié)點(diǎn)去中序中查看區(qū)分出誰是左子樹誰是右子樹3) 根據(jù)中序知道了左右子樹之后再去后序中找對(duì)應(yīng)的子樹后序結(jié)果方法說明size() - 獲取樹中結(jié)點(diǎn)的個(gè)數(shù) - 通過遞歸來完成遞歸的初始條件是 rootnull 時(shí) return 0 遞歸公式是1 size(root.left) size(root.right) 樹的節(jié)點(diǎn)個(gè)數(shù)等于1左子樹的節(jié)點(diǎn)個(gè)數(shù)右子樹的節(jié)點(diǎn)個(gè)數(shù)getLeafCount(TreeNode root) - 獲取葉子節(jié)點(diǎn)的個(gè)數(shù) - 遞歸來完成 - 初始條件是空樹情況下rootnull葉子節(jié)點(diǎn)的個(gè)數(shù)顯然為0當(dāng)root的左右子樹都為空時(shí)該節(jié)點(diǎn)root就是葉子節(jié)點(diǎn) 遞推公式時(shí) getLeafCount(root.left) getLeafCount(root.right)一棵樹的葉子節(jié)點(diǎn)就是左子樹和右子樹的葉子節(jié)點(diǎn)相加getKLevelCount(TreeNode root , int k) - 獲取第k層的葉子節(jié)點(diǎn)個(gè)數(shù)- 初始條件是ifrootnull || kkreturn 0 ifk 1 return 1 - 遞推公式是 一棵樹的第k層葉子節(jié)點(diǎn)個(gè)數(shù)左子樹第k-1層右子樹的第k-1層的葉子節(jié)點(diǎn)個(gè)數(shù)getHeight(TreeNode root) - 獲取書的最大高度 - 初始條件root null return 0 root.left null root.right null return1遞推公式1Math.max(getHeight(root.left) , getHeight(root.right)find(TreeNode root , int val) - 查找節(jié)點(diǎn) - 也是通過遞歸來實(shí)現(xiàn)的先判定樹為空的情況返回null再判定該樹的節(jié)點(diǎn)值是否等于val 等于就直接返回未找到再遞歸左子樹左子樹沒有再找右子樹通過遞歸的方式實(shí)現(xiàn)遍歷層序遍歷廣度優(yōu)先搜索 沒有遞歸通過隊(duì)列來實(shí)現(xiàn)獲取樹種結(jié)點(diǎn)的個(gè)數(shù)獲取樹中葉子節(jié)點(diǎn)的個(gè)數(shù)獲取第k層葉子節(jié)點(diǎn)的個(gè)數(shù)獲取數(shù)的最大高度查找節(jié)點(diǎn)判斷一棵樹是不是二叉樹