##給定一個二叉樹，回傳它的中序遍歷， 示例:
輸入: [1,null,2,3]
1
2
/
3
輸出: [1,3,2]
進階: 遞回演算法很簡單，你可以通過迭代演算法完成嗎？ 堆疊，
思路
時間復雜度O(n)，空間復雜度O(lgn)，
遞回代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private void recur(TreeNode root, List<Integer> ans) {
if(root != null) {
if(root.left != null) {
recur(root.left, ans);
}
ans.add(root.val);
if(root.right != null) {
recur(root.right, ans);
}
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
recur(root, ans);
return ans;
}
}
非遞回代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.add(curr.val);
curr = curr.right;
}
return ans;
}
}
鏈接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86908.html
標籤：其他
下一篇：鏈表