二叉樹的基本操作 - 遍歷
二叉樹的遍歷是非常重要的，因?yàn)槲覀円话銓?duì)樹做的很多操作基本上都是要建立在遍歷的基礎(chǔ)上的。
常件的遍歷方法方式有：
- 先序遍歷：先根、左子樹、右子樹
- 中序遍歷：左子樹、根、右子樹
- 后序遍歷：左子樹、右子樹、根
- 層次遍歷：從上到下、從左到右
各種遍歷的java實(shí)現(xiàn)在我的github上可以查看
例子：
- 輸出二叉樹中的葉子節(jié)點(diǎn)：
在遍歷二叉樹的算法中增加監(jiān)測(cè)結(jié)點(diǎn)的“左右子樹是否都為null”
void printLeaves（Node root）{
if(root != null){
if(root.left != null && root.right != null)
println(root.val);
printLeaves(root.left);
printLeaves(root.right);
}
}
- 求二叉樹的高度
我們只需要分別求出左右子樹的高度，然后取最高的。遞歸這個(gè)過(guò)程：
int getTreeHeight (Node root){
int leftH ,rightH, maxH;
if(root != null){
printLeaves(root.left);
printLeaves(root.right);
maxH = (leftH>rightH)?leftH:rightH;
return (maxH + 1);
}
}
- 由兩種遍歷序列確定一個(gè)二叉樹：
我們必須要通過(guò)前序遍歷或后序遍歷，結(jié)合著中序遍歷來(lái)確定一個(gè)二叉樹。如果前序遍歷和后序遍歷在一起我們無(wú)法確定根節(jié)點(diǎn)在哪。
Paste_Image.png
代碼在我的gitHub上可以查看。
