Go 刷 leetcode｜智慧樹下你和我

今天為大家講解 LeetCode 第 94 題，仍然繼續(xù)分享一道樹的題目。

題目描述

給定一個二叉樹，返回它的中序 遍歷。

示例:

輸入: [1,null,2,3] 1
2 / 3

輸出: [1,3,2] 進階: 遞歸算法很簡單，你可以通過迭代算法完成嗎？

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

先簡單介紹下樹的前中后序遍歷。

無論是哪種遍歷方法，考查節(jié)點的順序都是一樣的(思考做試卷的時候，人工遍歷考查順序)。只不過有時候考查了節(jié)點，將其暫存，需要之后的過程中輸出。

如上圖所示，三種遍歷方法(人工)得到的結(jié)果分別是：

先序：1 2 4 6 7 8 3 5 中序：4 7 6 8 2 1 3 5 后序：7 8 6 4 2 5 3 1

三種遍歷方法的考查順序一致，得到的結(jié)果卻不一樣，原因在于：

先序：考察到一個節(jié)點后，即刻輸出該節(jié)點的值，并繼續(xù)遍歷其左右子樹。(根左右)

中序：考察到一個節(jié)點后，將其暫存，遍歷完左子樹后，再輸出該節(jié)點的值，然后遍歷右子樹。(左根右)

后序：考察到一個節(jié)點后，將其暫存，遍歷完左右子樹后，再輸出該節(jié)點的值。(左右根)

方法一：遞歸

樹的結(jié)構(gòu)具有天然的遞歸性，使用遞歸還是比較容易的。不多說上代碼。

//go
//*?Definition?for?a?binary?tree?node.
type?TreeNode?struct?{
?Val?int
?Left?*TreeNode
?Right?*TreeNode
}

var?res?[]int

func?inorderTraversal(root?*TreeNode)?[]int?{
????res?=?make([]int,?0)
????inorder(root)
????return?res
}

func?inorder(root?*TreeNode)?{
????if?root?!=?nil?{
????????inorder(root.Left)?
????????res?=?append(res,?root.Val)
????????inorder(root.Right)
????}
}

//java
class?Solution?{
????public?List??inorderTraversal(TreeNode?root)?{
????????List??res?=?new?ArrayList??();
????????helper(root,?res);
????????return?res;
????}

????public?void?helper(TreeNode?root,?List??res)?{
????????if?(root?!=?null)?{
????????????if?(root.left?!=?null)?{
????????????????helper(root.left,?res);
????????????}
????????????res.add(root.val);
????????????if?(root.right?!=?null)?{
????????????????helper(root.right,?res);
????????????}
????????}
????}
}

方法二：遍歷

這是在題解中看到一個不錯也挺好理解的優(yōu)化方法，這里分享一下@henry

其核心思想如下：

• 使用顏色標(biāo)記節(jié)點的狀態(tài)，新節(jié)點為白色，已訪問的節(jié)點為灰色。
• 如果遇到的節(jié)點為白色，則將其標(biāo)記為灰色，然后將其右子節(jié)點、自身、左子節(jié)點依次入棧。
• 如果遇到的節(jié)點為灰色，則將節(jié)點的值輸出。

如要實現(xiàn)前序、后序遍歷，只需要調(diào)整左右子節(jié)點的入棧順序即可。

//go

type?ColorNode?struct?{
?node?*TreeNode
?color?string
}

func?inorderTraversal(root?*TreeNode)?[]int?{
?if?root?==?nil?{
??return?[]int{}
?}
?var?res?[]int
?var?stack?[]*ColorNode
?stack?=?append(stack,?&ColorNode{root,?"white"})
?var?cn?*ColorNode

?for?len(stack)?!=?0?{
??cn?=?stack[len(stack)-1]
??stack?=?stack[:len(stack)-1]?//?以上兩句等同于?cn?=?stack.pop()?，別忘了加這句
??if?cn.color?==?"white"?{
???//?因為棧是先進后出，所以中序是?右-根-左?的順序添加
???if?cn.node.Right?!=?nil?{
????stack?=?append(stack,?&ColorNode{cn.node.Right,"white"})
???}
???stack?=?append(stack,&ColorNode{cn.node,?"gray"})
???if?cn.node.Left?!=?nil?{
????stack?=?append(stack,?&ColorNode{cn.node.Left,?"white"})
???}
??}else?{
???res?=?append(res,?cn.node.Val)
??}
?}

?return?res
}

//java
class?Solution?{
????class?ColorNode?{
????????TreeNode?node;
????????String?color;
????????
????????public?ColorNode(TreeNode?node,String?color){
????????????this.node?=?node;
????????????this.color?=?color;
????????}
????}
????public?List?inorderTraversal(TreeNode?root)?{
????????if(root?==?null)?return?new?ArrayList();
????????????
????????List?res?=?new?ArrayList<>();
????????Stack?stack?=?new?Stack<>();
????????stack.push(new?ColorNode(root,"white"));
????????
????????while(!stack.empty()){
????????????ColorNode?cn?=?stack.pop();
????????????
????????????if(cn.color.equals("white")){
????????????????if(cn.node.right?!=?null)?stack.push(new?ColorNode(cn.node.right,"white"));
????????????????stack.push(new?ColorNode(cn.node,"gray"));
????????????????if(cn.node.left?!=?null)stack.push(new?ColorNode(cn.node.left,"white"));
????????????}else{
????????????????res.add(cn.node.val);
????????????}
????????}
????????
????????return?res;
????}
}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～