資訊專欄INFORMATION COLUMN
摘要：小鹿題目二叉樹中序遍歷給定一個二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環來實現。
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）二叉樹的前、中、后遍歷，首先明白前、中、后遍歷的順序是什么，對于二叉樹的中序遍歷來說，順序是左子樹節點 —> 根節點 —> 右子樹節點。2）通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環來實現。
遞歸法：1）判斷當前樹是否為空。
2）遞歸樹的左子樹結點。
3）輸出當前結點的值。
4）遞歸樹的右子樹節點。
迭代循環法：
1）聲明一個棧，將樹的左子節點入棧。
2）每出棧一個結點，輸出當前結點的值，且將該結點的右子樹進行遍歷打印，保證每個出棧的結點輸出值之后，再輸出上一個左子節點之前，將當前結點的右子節點遍歷畢。
3）整棵樹遍歷完畢的終止條件就是當前棧是否存在結點（樹的左子節點）。
var inorderTraversal = function(root) {
let arr = []
const inorder = root =>{
// 判斷當前的結點是否為空
if(root == null) return null;
// 遞歸左子樹
inorder(root.left)
// 輸出結點值
arr.push(root.val)
// 遞歸右子樹
inorder(root.right)
}
inorder(root)
return arr
};
// 迭代實現二叉樹的中序遍歷
var inorderTraversal = function(root) {
let stack = [];
let result = [];
while(true){
// 判斷樹是否為空
if(root == null) return result;
// 先將樹的左子節點推入棧中
while(root !== null){
stack.push(root);
root = root.left;
}
// 遍歷的終止條件
if(stack.length !== 0){
// 輸出棧中的結點
let temp = stack.pop();
result.push(temp.val);
// 如果當前存在右子節點，要先打印右子樹節點
root = temp.right;
}else{
break;
}
}
return result;
}
1）試著分別寫出前序遍歷、后序遍歷的遞歸實現和迭代實現代碼。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/104155.html
摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...
摘要：解法二迭代中序遍歷分析作者二叉搜索樹的中序后繼是中序遍歷中當前節點之后最小的節點。 文章目錄 1. 題目1.1 示例1.2 說明1.3 限制 2....
摘要：樹的前序，中序遍歷的結構如下圖可以看出，通過前序遍歷可以確定根節點，再通過中序遍歷和根節點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。 從前序與中序遍歷序列構造二叉樹 今天帶來的是Leetcode上的一個經典題：從前序與中序遍歷序列構造二叉樹原題干： /** Definition for a binary ...
閱讀 2831·2021-09-28 09:45
閱讀 1507·2021-09-26 10:13
閱讀 897·2021-09-04 16:45
閱讀 3661·2021-08-18 10:21
閱讀 1084·2019-08-29 15:07
閱讀 2633·2019-08-29 14:10
閱讀 3147·2019-08-29 13:02
閱讀 2459·2019-08-29 12:31
