資訊專欄INFORMATION COLUMN
摘要：小鹿題目二叉樹中序遍歷給定一個二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環(huán)來實現(xiàn)。
Time：2019/4/25
Title:Binary Tree Inorder Traversal
Difficulty: Medium
Author:小鹿
Given a binary tree, return the inorder traversal of its nodes" values.
給定一個二叉樹，返回它的中序?遍歷。
Example:
Input: [1,null,2,3]
1
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
進階:?遞歸算法很簡單，你可以通過迭代算法完成嗎？solve:
1）二叉樹的前、中、后遍歷，首先明白前、中、后遍歷的順序是什么，對于二叉樹的中序遍歷來說，順序是左子樹節(jié)點 —> 根節(jié)點 —> 右子樹節(jié)點。2）通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環(huán)來實現(xiàn)。
遞歸法：1）判斷當(dāng)前樹是否為空。
2）遞歸樹的左子樹結(jié)點。
3）輸出當(dāng)前結(jié)點的值。
4）遞歸樹的右子樹節(jié)點。
迭代循環(huán)法：
1）聲明一個棧，將樹的左子節(jié)點入棧。
2）每出棧一個結(jié)點，輸出當(dāng)前結(jié)點的值，且將該結(jié)點的右子樹進行遍歷打印，保證每個出棧的結(jié)點輸出值之后，再輸出上一個左子節(jié)點之前，將當(dāng)前結(jié)點的右子節(jié)點遍歷畢。
3）整棵樹遍歷完畢的終止條件就是當(dāng)前棧是否存在結(jié)點（樹的左子節(jié)點）。
var inorderTraversal = function(root) {
let arr = []
const inorder = root =>{
// 判斷當(dāng)前的結(jié)點是否為空
if(root == null) return null;
// 遞歸左子樹
inorder(root.left)
// 輸出結(jié)點值
arr.push(root.val)
// 遞歸右子樹
inorder(root.right)
}
inorder(root)
return arr
};
// 迭代實現(xiàn)二叉樹的中序遍歷
var inorderTraversal = function(root) {
let stack = [];
let result = [];
while(true){
// 判斷樹是否為空
if(root == null) return result;
// 先將樹的左子節(jié)點推入棧中
while(root !== null){
stack.push(root);
root = root.left;
}
// 遍歷的終止條件
if(stack.length !== 0){
// 輸出棧中的結(jié)點
let temp = stack.pop();
result.push(temp.val);
// 如果當(dāng)前存在右子節(jié)點，要先打印右子樹節(jié)點
root = temp.right;
}else{
break;
}
}
return result;
}
1）試著分別寫出前序遍歷、后序遍歷的遞歸實現(xiàn)和迭代實現(xiàn)代碼。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104155.html
摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設(shè)一個二叉搜索樹具有如下特征節(jié)點的左子樹只包含小于當(dāng)前節(jié)點的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...
摘要：解法二迭代中序遍歷分析作者二叉搜索樹的中序后繼是中序遍歷中當(dāng)前節(jié)點之后最小的節(jié)點。 文章目錄 1. 題目1.1 示例1.2 說明1.3 限制 2....
摘要：樹的前序，中序遍歷的結(jié)構(gòu)如下圖可以看出，通過前序遍歷可以確定根節(jié)點，再通過中序遍歷和根節(jié)點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。 從前序與中序遍歷序列構(gòu)造二叉樹 今天帶來的是Leetcode上的一個經(jīng)典題：從前序與中序遍歷序列構(gòu)造二叉樹原題干： /** Definition for a binary ...
閱讀 2865·2021-09-28 09:45
閱讀 1530·2021-09-26 10:13
閱讀 935·2021-09-04 16:45
閱讀 3693·2021-08-18 10:21
閱讀 1118·2019-08-29 15:07
閱讀 2661·2019-08-29 14:10
閱讀 3173·2019-08-29 13:02
閱讀 2489·2019-08-29 12:31
