我的面試準(zhǔn)備過程--leetcode樹

wenyiweb 發(fā)布于2019-08-15 10:44 / 1117人閱讀

摘要：由遍歷結(jié)果反求樹分析遞歸分治，第一層需要找到相應(yīng)的遍歷結(jié)果，對數(shù)組來說，問題轉(zhuǎn)化為找下標(biāo)問題對前序中序遍歷結(jié)果來說前序左右中序左右因此，中序中的下標(biāo)可求，為對每一層來說，左子樹的長度為，右子樹的長度為，左子樹前序為至，中序為至，可以使

　由遍歷結(jié)果反求樹

分析：遞歸分治，第一層需要找到相應(yīng)的遍歷結(jié)果，對數(shù)組來說，問題轉(zhuǎn)化為找下標(biāo)問題
對前序、中序遍歷結(jié)果來說
前序：[root,[左],[右]]
中序:[[左],root,[右]]
因此，中序中root的下標(biāo)可求，為inorderPos

對每一層來說，左子樹的長度為leftLen = inorderPos，右子樹的長度為rightLen = inorder.length - 1 - leftLen，
左子樹前序為preorder[1 至 leftLen]，中序為inorder[0 至 leftLen - 1]，可以使用System.arraycopy(preorder, 1, leftPre, 0, leftLen),
System.arraycopy(inorder, 0, leftInorder, 0, leftLen);
右子樹前序為preorder[leftLen + 1 至 preorder.length - 1]，中序為inorder[leftLen + 1 至 inorder.lenth - 1]，可以使用System.arraycopy(preorder, leftLen + 1, rightPre, 0, rightLen)，System.arraycopy(inorder, leftLen + 1, rightInorder, 0, rightLen);

對中序、后序來說，
中序:[[左],root,[右]]
后序：[[左],[右],root]

Leetcode 105 由前序、中序構(gòu)建樹

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0 || inorder.length == 0 || preorder.length != inorder.length){
        return null;
    }

    int len = preorder.length;
    TreeNode root = new TreeNode(preorder[0]);
    int inorderPos = 0;
    for(; inorderPos < inorder.length; inorderPos++){
        if(inorder[inorderPos] == root.val){
            break;
        }
    }

    int leftLen = inorderPos;
    int rightLen = len - inorderPos - 1;

    int[] leftPre = new int[leftLen];
    int[] leftInorder = new int[leftLen];

    int[] rightPre = new int[rightLen];
    int[] rightInorder = new int[rightLen];

    for(int i = 0; i < leftLen; i++){
        leftPre[i] = preorder[i + 1];
        leftInorder[i] = inorder[i];
    }

    for(int i = 0; i < rightLen; i++){
        rightPre[i] = preorder[leftLen + 1 + i];
        rightInorder[i] = inorder[leftLen + 1 + i];
    }

    TreeNode left = buildTree(leftPre, leftInorder);
    TreeNode right = buildTree(rightPre, rightInorder);

    root.left = left;
    root.right = right;

    return root;
}

Leetcode 106 由中序、后序構(gòu)建樹

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder.length == 0 || postorder.length == 0){
        return null;
    }

    int len = postorder.length;
    TreeNode root = new TreeNode(postorder[len - 1]);

    int inorderPos = 0;

    for(; inorderPos < len; inorderPos++){
        if(inorder[inorderPos] == root.val){
            break;
        }
    }

    int leftLength = inorderPos;
    int rightLength = len - inorderPos - 1;

    int[] leftInorder = new int[leftLength];
    int[] leftPost = new int[leftLength];

    int[] rightInorder = new int[rightLength];
    int[] rightPost = new int[rightLength];

    for(int i = 0; i < leftLength; i++){
        leftInorder[i] = inorder[i];
        leftPost[i] = postorder[i];
    }

    for(int i = 0; i < rightLength; i++){
        rightInorder[i] = inorder[inorderPos + 1 + i];
        rightPost[i] = postorder[leftLength + i];
    }

    TreeNode left = buildTree(leftInorder, leftPost);
    TreeNode right = buildTree(rightInorder, rightPost);

    root.left = left;
    root.right = right;

    return root;

}

　leetcode 124

思路：
分治：對于每一個結(jié)點來說，需要計算，當(dāng)前值＋左結(jié)點＋右結(jié)點與最大值的比較，同時，左結(jié)點與右結(jié)點的值通過遞歸得到，因此，遞歸的返回值應(yīng)是一條路徑的和

public class Solution{
  int maxNum = Integer.MIN_VALUE;
  public int maxPathSum(TreeNode root){

      if(root == null){
        return 0;
      }
      count(root);
      return maxNum;
  }

  public int count(TreeNode root){
    int lval = Integer.MIN_VALUE, rval = Integer.MIN_VALUE;
    int val = root.val;

    if(root.left != null){
      lval = count(root.left);
    }

    if(root.right != null){
      rval = count(root.right);
    }

    val = val + Math.max(lval, 0) + Math.max(rval, 0);

    if(val > maxNum){
      maxNum = val;
    }

    return root.val + Math.max(Math.max(lval, rval), 0);
  }  
}

最小深度與最大深度 leetcode 111 最小深度

遞歸法：
思路：

退出條件

root == null,直接返回0，但是！如果root.left或root.right其中一個為null，不能退出遞歸，兩種解決方法
方法一：使用新的遞歸函數(shù)規(guī)避

public int minDepth(TreeNode root){
  if(root == null){
    return 0;
  }
  return getMin(root);
}
public int getMin(TreeNode root){
  //規(guī)避左右子樹某一個為null
  if(root == null){
    return Integer.MAX_VALUE;//排除此條路徑
  }

  if(root.left == null && root.right == null){
    return 1;
  }
  int left = Integer.MAX_VALUE;
  int right = Integer.MAX_VALUE;

  if(root.left != null){
    left = getMin(root.left);
  }
  if(root.right != null){
    right = getMin(root.right);
  }

  return Math.min(left, right) + 1;
}

方法二：給當(dāng)前方法打補丁

public int minDepth(TreeNode root) {
      if(root == null){
        return 0;
      }

      if(root.left == null && root.right == null){
        return 1;
      }

      if(root.left == null){
          return minDepth(root.right) + 1;
      }else if(root.right == null){
          return minDepth(root.left) + 1;
      }else{
          return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
      }
}

root.left == null && root.right == null 說明為葉子結(jié)點，返回1

當(dāng)前層數(shù)加左右子樹的最小深度

迭代法
思路：層級遍歷，一旦在當(dāng)前層發(fā)現(xiàn)葉子結(jié)點，返回層數(shù)

  public int minDepth(TreeNode root){
    if(root == null){
      return 0;
    }
    if(root.left == null && root.right == null){
      return 1;
    }

    int depth = 0;
    int curLevelNodes = 1;
    int nextLevelNodes = 0;
    Queue queue = new LinkedList<>();
    queue.add(root);

    while(!queue.isEmpty()){
      TreeNode cur = queue.poll();
      curLevelNodes--;

      if(cur.left == null && cur.right == null){
        return depth + 1;
      }

      if(cur.left != null){
        queue.add(cur.left);
        nextLevelNodes++;
      }

      if(cur.right != null){
        queue.add(cur.right);
        nextLevelNodes++;
      }

      if(curLevelNodes == 0){
        depth++;
        curLevelNodes = nextLevelNodes;
        nextLevelNodes = 0;
      }
    }

    return depth;
  }

leetcode 104 最大深度

遞歸法
思路：遞歸時邏輯是一貫的

  public int getMaxDepth(TreeNode root){
    if(root == null){
      return 0;
    }

    return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
  }

迭代法
思路：層級遍歷求最大深度

  public int maxDepth(TreeNode root){
    if(root == null){
      return 0;
    }
    if(root.left == null && root.right == null){
      return 1;
    }

    int depth = 0;
    int curLevelNodes = 1;
    int nextLevelNodes = 0;
    Queue queue = new LinkedList<>();
    queue.add(root);

    while(!queue.isEmpty()){
      TreeNode cur = queue.poll();
      curLevelNodes--;

      if(cur.left != null){
        queue.add(cur.left);
        nextLevelNodes++;
      }

      if(cur.right != null){
        queue.add(cur.right);
        nextLevelNodes++;
      }

      if(curLevelNodes == 0){
        depth++;
        curLevelNodes = nextLevelNodes;
        nextLevelNodes = 0;
      }
    }

    return depth;
  }

leetcode 110 樹是否平衡

樹平衡要求對所有結(jié)點來說，其左右子樹的深度差不超過1

public boolean isBalanced(TreeNode root){
  if(root == null){
    return true;
  }

  int leftDepth = getMaxDepth(root.left);
  int rightDepth = getMaxDepth(root.right);

  if(Math.abs(leftDepth - rightDepth) > 1){
    return false;
  }

  return isBalanced(root.left) && isBalanced(root.right);
}

leetcode 100 判斷兩棵樹是否相同

分析：樹的相同，首先結(jié)構(gòu)相同，其次結(jié)點值相同
兩種判斷結(jié)構(gòu)是否相同的寫法，邏輯一樣
方法一

  public boolean isSame(TreeNode r1, TreeNode r2){
    if(r1 == null && r2 == null){
      return true;
    }
    if(r1 == null || r2 == null){
      return false;
    }
    //else 結(jié)構(gòu)相同
  }

方法二

  public boolean isSame(TreeNode r1, TreeNode r2){
    if(r1 == null){
      return r2 == null;
    }

    if(r2 == null){
      return false;
    }
    //else 結(jié)構(gòu)相同
  }

完整邏輯

  public boolean isSame(TreeNode r1, TreeNode r2){
    if(r1 == null){
      return r2 == null;
    }

    if(r2 == null){
      return false;
    }

    return r1.val == r2.val && isSame(r1.left, r2.left) && isSame(r1.right, r2.right);
  }

leetcode 101 判斷對稱

左右子樹，結(jié)構(gòu)相同，對稱位置值相同

public boolean isSymmetric(TreeNode root) {
  if(root == null){
    return true;
  }
  return help(root.left, root.right);
}

public boolean help(TreeNode p, TreeNode q){
  if(p == null){
    return q == null;
  }
  if(q == null){
    return false;
  }

  return p.val == q.val && help(p.left, q.right) && help(p.right, q.left);
}

leetcode 98 判斷二叉搜索樹

迭代法
思路：中序遍歷前一個結(jié)點值小于后面的結(jié)點值

public boolean isValidBST(TreeNode root){
  if(root == null){
    return true;
  }

  Stack stack = new Stack<>();
  TreeNode cur = root;

  TreeNode preCur = null;
  while(true){
    while(cur != null){
        stack.push(cur);
        cur = cur.left;
      }

      if(stack.isEmpty()){
        break;
      }

      cur = stack.pop();

      if(preCur != null){
        if(preCur.val >= cur.val){
          return false;
        }
      }
      preCur = cur;
      cur = cur.right;
  }  
  return true;
}

遞歸法
思路：同樣是中序遍歷

思考 pre結(jié)點在哪賦值，賦值前如何處理

    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
          return true;
        }

        if(root.left == null && root.right == null){
            return true;
        }

        return help(root);
    }

    public boolean help(TreeNode root){
        if(root == null){
            return true;
        }

        boolean left = help(root.left);
        if(pre != null && pre.val >= root.val){
            return false;
        }
        pre = root;
        boolean right = help(root.right);
        return left && right;
    }

鏈表與樹 leetcode 114 二叉樹轉(zhuǎn)鏈表

思路：斷開每一個結(jié)點，從用一個指針遞歸地向下指，每次都只更新右結(jié)點，遞歸順序為先左子樹，后右子樹

  TreeNode pointer = new TreeNode(-1);
  public void flatten(TreeNode root){
    if(root == null){
      return;
    }
    TreeNode left = root.left;
    TreeNode right = root.right;
    root.left = null;
    root.right = null;
    pointer.right = root;
    pointer = root;

    flatten(root.left);
    flatten(root.right);
  }

鏈表轉(zhuǎn)二叉樹

O(nlogn)解法

public TreeNode sortedListToBST(ListNode head){
       if(head == null){
         return null;
       }
       if(head.next == null){
           return new TreeNode(head.val);
       }
       int length = 0;
       ListNode cur = head;
       while(cur != null){
         cur = cur.next;
         length++;
       }
       return help(head, length);
 }
   public TreeNode help(ListNode head, int length){
     if(length == 0){
       return null;
     }

     ListNode now = head;
     for(int i = 0; i < (length - 1) >> 1; i++){
       now = now.next;
     }
     TreeNode root = new TreeNode(now.val);

     TreeNode left = help(head, (length - 1) >> 1);
     TreeNode right = help(now.next, length >> 1);

     root.left = left;
     root.right = right;

     return root;
   }

O(n)解法
將鏈表先轉(zhuǎn)成數(shù)組

leetcode 108 數(shù)組轉(zhuǎn)平衡二叉樹

public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0){
            return null;
        }

        if(nums.length == 1){
            return new TreeNode(nums[0]);
        }

        int length = nums.length;
        int now = nums[(length - 1) >> 1];
        TreeNode root = new TreeNode(now);
        int leftLen = (length - 1) >> 1;
        int rightLen = length >> 1;

        int[] leftArr = new int[leftLen];
        int[] rightArr = new int[rightLen];
        System.arraycopy(nums, 0, leftArr, 0, leftLen);
        System.arraycopy(nums, leftLen + 1, rightArr, 0, rightLen);

        root.left = sortedArrayToBST(leftArr);
        root.right = sortedArrayToBST(rightArr);

        return root;
    }

云服務(wù)器 GPU云服務(wù)器 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67314.html

發(fā)表評論

登陸后可評論

0條評論

wenyiweb

男|高級講師

我要關(guān)注我要私信

TA的文章

云計算災(zāi)難恢復(fù)最佳實踐

閱讀 1074·2021-11-15 18:11
國內(nèi)主機是什么-國內(nèi)主機游戲市場冷淡的原因是什么？

閱讀 3201·2021-09-22 15:33
恒創(chuàng)科技：海外服務(wù)器、云服務(wù)器、高防，3折起，可選香港/美國服務(wù)器

閱讀 3493·2021-09-01 11:42
RackNerd： KVM年付9.49美元起,Intel或AMD Ryzen,洛杉磯/西雅圖/圣何塞

閱讀 2691·2021-08-24 10:03
HostSailor：羅馬尼亞機房，內(nèi)容寬松，VPS七折優(yōu)惠，獨立服務(wù)器95折

閱讀 3643·2021-07-29 13:50
（知識）width、naturalWidth、clientWidth、offsetWidth區(qū)別整理

閱讀 2952·2019-08-30 14:08
寫css的毛病

閱讀 1299·2019-08-28 17:56
原生JS實現(xiàn)data方法

閱讀 2285·2019-08-26 13:57

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

我的面試準(zhǔn)備過程--leetcode樹

相關(guān)文章

**前端該如何準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和算法？**

金三銀四背后，一個 Android 程序員的面試心得

**大廠算法面試之leetcode精講7.雙指針**

發(fā)表評論

0條評論

wenyiweb

男|高級講師

TA的文章

云計算災(zāi)難恢復(fù)最佳實踐

國內(nèi)主機是什么-國內(nèi)主機游戲市場冷淡的原因是什么？

恒創(chuàng)科技：海外服務(wù)器、云服務(wù)器、高防，3折起，可選香港/美國服務(wù)器

RackNerd： KVM年付9.49美元起,Intel或AMD Ryzen,洛杉磯/西雅圖/圣何塞

HostSailor：羅馬尼亞機房，內(nèi)容寬松，VPS七折優(yōu)惠，獨立服務(wù)器95折

（知識）width、naturalWidth、clientWidth、offsetWidth區(qū)別整理

寫css的毛病

原生JS實現(xiàn)data方法

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

我的面試準(zhǔn)備過程--leetcode樹

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！