iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 17
0
自我挑戰組

刷題記錄與人生分享系列 第 17

DAY17 Binary Tree Inorder Traversal

  • 分享至 

  • xImage
  •  

題目:

https://leetcode.com/problems/binary-tree-inorder-traversal/
中序排序法訪問順序為左節點->根節點->右節點。

解題思路:

利用遞迴的觀念,訪問左節點後直到為空,接續訪問根節點直到為空,最後訪問右節點。

C版本:

void recursive(struct TreeNode* parent, int* recursiveResult, int* recursiveSize){
    if(parent==NULL){
        return;
    }
    
    if(parent->left==NULL && parent->right==NULL){
        recursiveResult[*recursiveSize]=parent->val;
        (*recursiveSize)++;
        return;
    }
		
    if(parent->left!=NULL){
        recursive(parent->left, recursiveResult, recursiveSize);
    }
    
    recursiveResult[*recursiveSize]=parent->val;
    (*recursiveSize)++;
    
    if(parent->right!=NULL){
        recursive(parent->right, recursiveResult, recursiveSize);
    }
		
    return;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* traversalResult=(int*)malloc(1000*sizeof(struct TreeNode));
    
    recursive(root, traversalResult, returnSize);
    return traversalResult;
}

Javascript版本:

var inorderTraversal = function(root) {
  const stack = [];
  const res = [];

  while (root || stack.length) {
    if (root) {
      stack.push(root);
      root = root.left;
    } else {
      root = stack.pop();
      res.push(root.val);
      root = root.right;
    }
  }
  return res;
};

函示解釋:

Push() 將值放入陣列
Pop() 將值從陣列最後取出

程式Github分享:

https://github.com/SIAOYUCHEN/leetcode

相似主題分享:

https://ithelp.ithome.com.tw/users/20100009/ironman/2500
https://ithelp.ithome.com.tw/users/20113393/ironman/2169
https://ithelp.ithome.com.tw/users/20107480/ironman/2435
https://ithelp.ithome.com.tw/users/20107195/ironman/2382
https://ithelp.ithome.com.tw/users/20119871/ironman/2210
https://ithelp.ithome.com.tw/users/20106426/ironman/2136

本日分享:
Everyone who pursues a dream has a silent time, a day that only oneself knows, sometimes I spend a lot of effort and endure a lot of loneliness and loneliness.
每個追求夢想的人,都有一段沉默的時光, 一段只有自己知道的日子, 有時候,付出了很多努力,有時候也忍受了很多的孤獨和寂寞。


上一篇
DAY16 Merge Two Sorted Lists
下一篇
DAY18 Same Tree
系列文
刷題記錄與人生分享34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言