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