劍指offer閱讀（三）

<h2>劍指offer(三)</h2>

<h3>面試題二十五：二叉樹中和為某一值的路徑</h3>

<blockquote>
題目：輸入一棵二叉樹和一個(gè)整數(shù)铆惑，打印出二叉樹中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑本冲。從樹的根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成一條路徑责掏。二叉樹的定義如下：
</blockquote>

<pre><code class="java">class BinartTreeNode{
int m_nValue;
BinaryTreeNode left;
BinaryTreeNode right;
}
</code></pre>

<pre><code class="java">package offer;

import java.util.LinkedList;

/**

  • Created by KiSoo on 2017/2/2.
    */
    public class Offer25 {
    public static void main(String... args) {
    TreeNode node = new TreeNode(10);
    TreeNode node1 = new TreeNode(5);
    TreeNode node2 = new TreeNode(4);
    TreeNode node3 = new TreeNode(7);
    TreeNode node4 = new TreeNode(12);
    node.left = node1;
    node.right = node4;
    node1.left = node2;
    node1.right = node3;
    findPath(node,22);
    }

    public static void findPath(TreeNode root, int expectedSum) {
    LinkedList<Integer> path = new LinkedList<>();
    int currentSum = 0;
    findPath(root, expectedSum, path, currentSum);
    }

    private static void findPath(TreeNode root, int expectedSum, LinkedList<Integer> path, int currentSum) {
    currentSum += root.value;
    path.add(root.value);
    boolean isLeaf = root.left == null && root.right == null;
    if (currentSum == expectedSum && isLeaf) {
    for (int i : path)
    Utils.syso(i);
    System.out.println("---");
    }
    if (root.left != null)
    findPath(root.left, expectedSum, path, currentSum);
    if (root.right != null)
    findPath(root.right, expectedSum, path, currentSum);
    path.removeLast();
    }

}

</code></pre>

思路：使用一個(gè)鏈表把所有路過的點(diǎn)都記錄下來，使用前序遍歷，當(dāng)退出當(dāng)前節(jié)點(diǎn)的時(shí)候，removelast收奔，函數(shù)棧的思想。

<h3>面試題二十六：復(fù)雜鏈表的復(fù)制</h3>

<blockquote>
題目：請(qǐng)實(shí)現(xiàn)函數(shù)ComplexListNode* Clone(ComplexListNode* head)復(fù)制一個(gè)復(fù)雜鏈表办桨，在復(fù)雜鏈表中筹淫，每個(gè)節(jié)點(diǎn)除了有一個(gè)next的指針指向下一個(gè)節(jié)點(diǎn)外，還有一個(gè)sibling指向鏈表中的任意節(jié)點(diǎn)或者NULL呢撞。節(jié)點(diǎn)的C++定義如下：
</blockquote>

<pre><code>struct ComplexListNode{
int value;
ComplexListNode* m_pNext;
ComplexListNode* m_pSibling;
}
</code></pre>

<pre><code> public static ComplexListNode cloneNode(ComplexListNode refrence) {
cloneNodes(refrence);
connectSiblingNode(refrence);
return reconnectNodes(refrence);
}

private static ComplexListNode reconnectNodes(ComplexListNode refrence) {
    ComplexListNode clonedHead = null;
    ComplexListNode clonedNode = null;
    if (refrence != null) {
        clonedHead = clonedNode = refrence.next;
        refrence.next = clonedHead.next;
        refrence = refrence.next;
    }
    while (refrence != null) {
        clonedNode.next = refrence.next;
        clonedNode = clonedNode.next;
        refrence.next = clonedNode.next;
        refrence = refrence.next;
    }
    return clonedHead;
}

private static void connectSiblingNode(ComplexListNode refrence) {
    while (refrence != null) {
        ComplexListNode cloned = refrence.next;
        if (refrence.sibling != null) {
            cloned.sibling = refrence.sibling.next;
        }
        refrence = cloned.next;
    }
}

private static void cloneNodes(ComplexListNode refrence) {
    if (refrence == null)
        throw new NullPointerException("invaild paramer");
    while (refrence != null) {
        ComplexListNode cloned = new ComplexListNode(refrence.value);
        cloned.next = refrence.next;
        cloned.sibling = null;
        refrence.next = cloned;
        refrence = cloned.next;
    }
}

</code></pre>

<h4>三次遍歷</h4>

<blockquote>
思路：先遍歷一便损姜，在每個(gè)node后復(fù)制自身，然后殊霞，再次遍歷摧阅，讓node的clone指向node的隨機(jī)node的下一個(gè)，再次遍歷绷蹲，連接所有node的clone棒卷，返回nodeHead。
</blockquote>

<h3>面試題二十七：二叉搜索樹與雙向鏈表（懵）</h3>

<blockquote>
題目：輸入一棵二叉搜索樹祝钢，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表比规。要求不能創(chuàng)建任何新的節(jié)點(diǎn)，只能調(diào)整數(shù)中節(jié)點(diǎn)指針的指向拦英。
</blockquote>

<h4>思路</h4>

中序遍歷+將真正的頭節(jié)點(diǎn)和當(dāng)前頭節(jié)點(diǎn)存儲(chǔ)在一起蜒什。

<pre><code> public class Solution {
TreeNode head = null;
TreeNode realHead = null;

    public TreeNode convert(TreeNode root) {
        convertSub(root);
        return realHead;
    }

    public void convertSub(TreeNode node) {
        if (node == null)
            return;
        convertSub(node);
        if (head == null) {
            head = node;
            realHead = node;
        } else {
            head.right = node;
            node.left = head;
            head = node;
        }
        convertSub(node.right);
    }
}

</code></pre>

<h3>面試題二十八：字符串的排列</h3>

<blockquote>
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列疤估。例如輸入字符串a(chǎn)bc灾常，則打印出a、b铃拇、c所能排列出來的所有字符串钞瀑。
</blockquote>

<pre><code>package offer;

/**

  • Created by KiSoo on 2017/2/2.
    */
    public class Offer28 {

    /**

    • 題目：輸入一個(gè)字符串，打印出該字符事中字符的所有排列慷荔。例如輸入字符串a(chǎn)bc雕什。
    • 則打印出由字符a、b显晶、c 所能排列出來的所有字符串a(chǎn)bc贷岸、acb、bac吧碾、bca凰盔、cab和cba。
    • @param chars 待排序的字符數(shù)組
      */
      public static void permutation(char[] chars) {
      // 輸入較驗(yàn)
      if (chars == null || chars.length < 1) {
      return;
      }
      // 進(jìn)行排列操作
      permutation(chars, 0);
      }

    /**

    • 求字符數(shù)組的排列

    • @param chars 待排列的字符串

    • @param begin 當(dāng)前處理的位置
      */
      public static void permutation(char[] chars, int begin) {
      // 如果是最后一個(gè)元素了倦春，就輸出排列結(jié)果
      if (chars.length - 1 == begin) {
      System.out.print(new String(chars) + " ");
      } else {
      char tmp;
      // 對(duì)當(dāng)前還未處理的字符串進(jìn)行處理户敬，每個(gè)字符都可以作為當(dāng)前處理位置的元素
      for (int i = begin; i < chars.length; i++) {
      // 下面是交換元素的位置
      tmp = chars[begin];
      chars[begin] = chars[i];
      chars[i] = tmp;

           // 處理下一個(gè)位置
     permutation(chars, begin + 1);
 }

      }
      }

    public static void main(String[] args) {
    char[] c1 = {'a', 'b', 'c'};
    permutation(c1);
    System.out.println();

     char[] c2 = {'a', 'b', 'c', 'd'};
 permutation(c2);

    }

}

</code></pre>

<h3>面試題二十九：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字</h3>

<blockquote>
題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù)字睁本。例如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}尿庐。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半呢堰，因此輸出2抄瑟。
</blockquote>

<pre><code><br />static int moreThanHalfNum(int[] numbers) {
int result = numbers[0];
int times = 1;
for (int i = 1; i < numbers.length; i++) {
if (times == 0) {
result = numbers[i];
times = 1;
} else if (numbers[i] == result) {
times++;
} else {
times--;
}
}
if (checkMoreThanHalf(numbers, result))
return result;
else
return 0;
}

private static boolean checkMoreThanHalf(int[] numbers, int result) {
    int times = 0;
    for (int i = 0; i &lt; numbers.length; i++) {
        if (numbers[i] == result)
            times++;
    }
    boolean isMoreThanHalf = true;
    if (times * 2 &lt;= numbers.length) {
        isMoreThanHalf = false;
    }
    return isMoreThanHalf;
}

</code></pre>

<h4>思路</h4>

兩種方式：

  1. 快速排序，取中間值校驗(yàn)枉疼。
  2. 根據(jù)數(shù)組的特點(diǎn)皮假，選出出現(xiàn)次數(shù)最多的鞋拟，然后校驗(yàn)。

<h3>面試題三十：最小的k個(gè)數(shù)</h3>

<blockquote>
題目：輸入n個(gè)整數(shù)惹资，找出其中最小的k個(gè)數(shù)贺纲，例如輸入4、5褪测、1猴誊、6、2侮措、7懈叹、3、8這8個(gè)數(shù)字分扎，則最小的4個(gè)數(shù)字是1澄成、2、3笆包、4环揽。
</blockquote>

<h4>思路</h4>

<ol>
<li>基于數(shù)組左邊的第K個(gè)數(shù)字進(jìn)行快速排序，使得所有比第k個(gè)數(shù)字小的所有數(shù)字都位于數(shù)組的左邊</li>
<li>使用一個(gè)容器庵佣，裝填最小的k個(gè)數(shù)字歉胶，滿了以后從其中找出最大數(shù)，刪除巴粪。</li>
</ol>

<pre><code>/**

  • Created by kangqizhou on 2017/2/4.
    */
    public class Offer30 {

    /**

    • @param krr
    • @param k
    • @return
      */
      public static int[] minK(int krr[], int k) {
      int arr[] = new int[k];
      for (int i = 0; i < k; i++)
      arr[i] = krr[i];
      buildHeap(arr);
      for (int j = k; j < krr.length; j++) {
      if (krr[j] < arr[0]) {
      arr[0] = krr[j];
      maxHeap(arr, 1, k);
      }
      }
      return arr;
      }

    /**

    • 建最大堆
    • @param arr
      */
      public static void buildHeap(int arr[]) {
      int heapsize = arr.length;
      for (int i = arr.length / 2; i > 0; i--)
      maxHeap(arr, i, heapsize);
      }

    /**

    • 調(diào)整為最大堆
    • @param arr
    • @param i
    • @param heapsize
      */
      public static void maxHeap(int arr[], int i, int heapsize) {
      int largest = i;
      int left = 2 * i;
      int right = 2 * i + 1;
      if (left <= heapsize && arr[i - 1] < arr[left - 1])
      largest = left;
      if (right <= heapsize && arr[largest - 1] < arr[right - 1])
      largest = right;
      if (largest != i) {
      int temp = arr[i - 1];
      arr[i - 1] = arr[largest - 1];
      arr[largest - 1] = temp;
      maxHeap(arr, largest, heapsize);
      }
      }

    public static void main(String[] args) {
    int krr[] = {1, 3, 4, 2, 7, 8, 9, 10, 14, 16};
    int arr[] = minK(krr, 4);
    for (int i = 0; i < arr.length; i++)
    System.out.println(arr[i]);

    }

}

</code></pre>

<h3>面試題三十一：連續(xù)子數(shù)組的最大和</h3>

<blockquote>
題目：輸入一個(gè)整形數(shù)組通今，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中一個(gè)活連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組肛根。求所有子數(shù)組的和的最大值辫塌。要求時(shí)間復(fù)雜度為O(1)
</blockquote>

<h4>思路：</h4>

如果之前的子數(shù)組之和小于0，那就直接從新的數(shù)字開始做子數(shù)組派哲，每次更改后臼氨，就比較，取大值芭届。

<pre><code class="java">/**

  • Created by kangqizhou on 2017/2/6.
    */
    public class Offer31 {
    public static void main(String... args){
    int[] data = {1,2,3,-34,-2,-45,3,-4,12,6};
    Solution solution = new Solution();
    Utils.syso(solution.getBiggestNum(data));
    }

    private static class Solution{
    boolean inVaild = false;
    public int getBiggestNum(int[] data){
    if (data == null){
    inVaild = true;
    return 0;
    }
    inVaild = false;
    int nCurSum = 0;
    int biggestNum = 0x80000000;
    for (int i = 0;i < data.length;i++){
    if (nCurSum<=0)
    nCurSum = data[i];
    else
    nCurSum += data[i];
    if (nCurSum > biggestNum)
    biggestNum = nCurSum;
    }
    return biggestNum;
    }
    }
    }

</code></pre>

<h3>面試題三十二：從1到n整數(shù)中1出現(xiàn)的次數(shù)</h3>

<blockquote>
題目：輸入一個(gè)整數(shù)n储矩，求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)，例如輸入12褂乍，從1到12這些整數(shù)中包含1的數(shù)字有1持隧，10，11和12逃片，1一共出現(xiàn)了5次
</blockquote>

<h4>思路：</h4>

<ol>
<li>不考慮時(shí)間復(fù)雜度的情況下屡拨，遍歷每個(gè)數(shù)字，得到每個(gè)數(shù)字中1的個(gè)數(shù)，然后累加呀狼。</li>
<li>每次去掉最高位然后做遞歸裂允，遞歸的次數(shù)和位數(shù)相同。一個(gè)數(shù)字n有O(logn)位赠潦，因此這種思路的時(shí)間復(fù)雜度是O(logn)叫胖，比前面的原始方法藥好很多草冈。</li>
</ol>

<pre><code class="java"> public static class Solution32II {
public int NumberOf1Between1AndN_Solution(int num) {
if (num < 10)
return 1;
int firstPosition = num;
int length = 0;
//求得首位數(shù)字
while (firstPosition > 10) {
firstPosition = firstPosition / 10;
length++;
}
//求得剩余數(shù)字
int other = num - firstPosition * powerBase10(length);

        int numFirstDight = 0;
        if (firstPosition &gt; 1)
            numFirstDight = powerBase10(length);
        else if (firstPosition == 1)
            numFirstDight = other + 1;
        int numberOther = firstPosition * (length) * powerBase10(length - 1);
        return numFirstDight + numberOther + NumberOf1Between1AndN_Solution(other);
    }

    private int powerBase10(int n) {
        int result = 1;
        for (int i = 0; i &lt; n; ++i)
            result *= 10;
        return result;
    }
}

</code></pre>

<h3>面試題三十三：把數(shù)組排成最小的數(shù)</h3>

<blockquote>
題目：輸入一個(gè)正整數(shù)數(shù)組她奥，把數(shù)組里的所有數(shù)字拼接起來排成一個(gè)數(shù)，打印出能拼接的所有數(shù)字中最小的一個(gè)怎棱。例如輸入數(shù)組{3哩俭，32，321}拳恋，打印出最小的數(shù)字是{321323}凡资；
</blockquote>

<h4>思路：</h4>

使用快速排序，更改判定條件即可

<pre><code class="java">package offer;

/**

  • Created by KiSoo on 2017/2/6.
    */

public class Offer33 {
public static void main(String... args) {
int data[] = {321, 23, 1111};
Utils.syso(new Solution33().getNum(data));
}

public static class Solution33 {

    public String getNum(int[] data) {
        sort(data, 0, data.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i : data)
            sb.append(i);
        return sb.toString();
    }

    private void sort(int[] data, int left, int right) {
        if (left &lt; right) {
            int position = partition(data, left, right);
            if (position == left)
                sort(data, left + 1, right);
            if (position == right)
                sort(data, left, right - 1);
            else {
                sort(data, left, position - 1);
                sort(data, position + 1, right);
            }
        }
    }

    private int partition(int[] data, int left, int right) {
        int value = data[right];
        int n = left;
        for (int i = left; i &lt; right; i++) {
            if (isSmall(data[i], value)) {
                changeE(data, i, n);
                n++;
            }
        }
        changeE(data, n, right);
        return n;
    }

    public boolean isSmall(int m, int n) {
        String left = String.valueOf(m) + String.valueOf(n);
        String right = String.valueOf(n) + String.valueOf(m);
        for (int i = 0; i &lt; left.length(); i++) {
            if (left.charAt(i) &lt; right.charAt(i))
                return true;
            else if (left.charAt(i) &gt; right.charAt(i))
                return false;
        }
        return false;
    }

    private void changeE(int[] data, int i, int n) {
        if (i == n)
            return;
        data[i] = data[i] + data[n];
        data[n] = data[i] - data[n];
        data[i] = data[i] - data[n];
    }
}

}

</code></pre>

<h3>面試題三十四：丑數(shù)</h3>

<blockquote>
題目：我們把只包含印子2谬运、3隙赁、5的數(shù)稱為丑數(shù)。求按從小到大的順序的第1500個(gè)丑數(shù)梆暖，例如6伞访，8都是丑數(shù)，但14不是轰驳，因?yàn)樗蜃?厚掷。習(xí)慣上我們把1當(dāng)作第一個(gè)丑數(shù)。
</blockquote>

<pre><code class="java">package offer;

/**

  • Created by KiSoo on 2017/2/6.
    */
    public class Offer34 {
    public static void main(String... args) {
    Utils.syso(getUglyNum(4));
    }

    public static int getUglyNum(int index) {
    if (index <= 0)
    return 0;
    int[] uglyNum = new int[index];
    uglyNum[0] = 1;
    int nextUglyNumIndex = 1;
    int p2 = 0;
    int p3 = 0;
    int p5 = 0;
    while (nextUglyNumIndex < index) {
    int min = min(uglyNum[p2] * 2, uglyNum[p3] * 3, uglyNum[p5] * 5);
    uglyNum[nextUglyNumIndex] = min;
    while (uglyNum[p2] * 2 <= uglyNum[nextUglyNumIndex])
    p2++;
    while (uglyNum[p3] * 3 <= uglyNum[nextUglyNumIndex])
    p3++;
    while (uglyNum[p5] * 5 <= uglyNum[nextUglyNumIndex])
    p5++;
    nextUglyNumIndex++;
    }
    return uglyNum[index - 1];
    }

    private static int min(int i, int i1, int i2) {
    int min = i < i1 ? i : i1;
    return min < i2 ? min : i2;
    }

}

</code></pre>

<h3>面試題35：第一次只出現(xiàn)一次的字符级解。</h3>

<blockquote>
題目：在字符串中找出第一個(gè)只出現(xiàn)一次的字符冒黑。如輸入“abaccdeff”，則輸出‘b'勤哗。
</blockquote>

<pre><code class="java">package offer;

import java.util.HashMap;

/**

  • Created by KiSoo on 2017/2/6.
    */
    public class Offer35 {
    public static void main(String... args) {
    char[] str = {'a', 'b', 'c', 'a', 'b', 'a'};
    Utils.syso(firstNotRepeatingChar(str));
    }

    static char firstNotRepeatingChar(char[] str) {
    if (str == null)
    return '\0';
    HashMap<Character, Integer> hashMap = new HashMap<>();
    for (char c : str) {
    Integer times = hashMap.get(c);
    hashMap.put(c, times == null ? 1 : times + 1);
    }
    for (char c : str) {
    int i = hashMap.get(c);
    if (i == 1)
    return c;
    }
    return '\0';
    }
    }

</code></pre>

思路：

使用hashmap抡爹，遍歷兩次即可。

<h3>面試題三十六：數(shù)組中的逆序?qū)?lt;/h3>

<blockquote>
題目：在數(shù)組中的兩個(gè)數(shù)字如果前面一個(gè)大于后面的數(shù)字芒划，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Χ埂］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)腊状。
</blockquote>

<pre><code class="java">package offer;

/**

  • Created by KiSoo on 2017/2/6.
    */
    public class Offer36 {

    public static void main(String... args) {
    int[] a = {7, 5, 6, 4};
    Utils.syso(inversePairs(a));
    }

    public static int inversePairs(int[] data) {
    if (data == null) {
    return 0;
    }
    int[] copy = new int[data.length];
    for (int i = 0; i < data.length; i++)
    copy[i] = data[i];

     return inversePairsCore(data, copy, 0, data.length - 1);

    }

    private static int inversePairsCore(int[] data, int[] copy, int start, int end) {
    if (start == end) {
    copy[start] = data[start];
    return 0;
    }
    int length = (end - start) / 2;
    int left = inversePairsCore(copy, data, start, start + length);
    int right = inversePairsCore(copy, data, start + length + 1, end);
    int i = start + length;
    int j = end;
    int indexCopy = end;
    int count = 0;
    while (i >= start && j >= start + length + 1) {
    if (data[i] > data[j]) {
    copy[indexCopy--] = data[i--];
    count += j - start - length;
    } else {
    copy[indexCopy--] = data[j--];
    }
    }
    while (i >= start) {
    copy[indexCopy--] = data[i--];
    }
    while (j >= start + length + 1) {
    copy[indexCopy--] = data[j--];
    }
    return left + right + count;
    }

}

</code></pre>

<h3>面試題三十七：兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)诱咏。</h3>

<blockquote>
題目：輸入兩個(gè)鏈表，找出它們的第一個(gè)公共節(jié)點(diǎn)缴挖。
</blockquote>

<h4>思路：</h4>

先得出兩個(gè)鏈表的長度差袋狞，然后，先在長鏈表中走k步，然后同時(shí)走苟鸯，直到node相同同蜻。

<h3>面試題三十八：</h3>

<blockquote>
題目：統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)，例如輸入排序數(shù)組{1早处，2湾蔓，3，3砌梆，3默责，3，4咸包，5}和數(shù)字3桃序，由于3在這個(gè)數(shù)組中出現(xiàn)了4次，因此輸出4
</blockquote>

思路：使用二分查找先找出最左邊出現(xiàn)的k的下標(biāo)烂瘫，再找出最右邊出現(xiàn)的k的下標(biāo)媒熊。相減即可得到次數(shù)。

<pre><code>package offer;

/**

  • Created by KiSoo on 2017/2/7.
    */
    public class Offer38 {
    public static void main(String... str) {
    int[] a = {1, 2, 3, 3, 3, 4, 5};
    Utils.syso(getFirstK(a, 3));
    }

    public static int getFirstK(int data[], int k) {
    if (data == null)
    return -1;
    return getFirstK(data, k, 0, data.length - 1) - getLastK(data, k, 0, data.length - 1);
    }

    private static int getLastK(int[] data, int k, int left, int right) {
    if (left < right)
    return 0;
    int middleIndex = (left + right) / 2;
    int middleData = data[middleIndex];
    if (middleData == k) {
    if (middleIndex < data.length - 1 && data[middleIndex + 1] != k || middleIndex == data.length - 1) {
    return middleIndex;
    } else
    left = middleIndex + 1;
    } else if (middleData < k)
    left = middleIndex + 1;
    else if (middleData > k)
    right = middleIndex - 1;
    return getLastK(data, k, left, right);
    }

    private static int getFirstK(int[] data, int k, int left, int right) {
    if (left > right)
    return 0;
    int middleIndex = (left + right) / 2;
    int middleData = data[middleIndex];
    if (middleData == k) {
    if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0)
    return middleIndex;
    else
    right = middleIndex + 1;
    } else if (middleData > k)
    right = middleIndex - 1;
    else
    left = middleIndex + 1;
    return getFirstK(data, k, left, right);
    }

}

</code></pre>

<h3>面試題三十九：二叉樹的深度</h3>

<blockquote>
題目一：輸入一棵二叉樹的根節(jié)點(diǎn)坟比，求該樹的深度芦鳍。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過的節(jié)點(diǎn)形成的樹的一條路徑，最長路徑的長度為樹的深度葛账。
</blockquote>

<pre><code> private static int getHeight(TreeNode firstNode) {
if (firstNode == null)
return 0;
int left = getHeight(firstNode.left);
int right = getHeight(firstNode.right);
return left > right ? left + 1 : right + 1;
}
</code></pre>

<h4>思路：通過遞歸柠衅，取左右子樹的較大值加1。</h4>

<blockquote>
題目二：輸入一棵二叉樹的根節(jié)點(diǎn)注竿，判斷該樹是不是平衡二叉樹茄茁。如果某二叉樹中任意節(jié)點(diǎn)的左右子樹的深度相差不超過1，那么它就是一顆平衡二叉樹巩割。
</blockquote>

<pre><code> static boolean isBalanced(TreeNode node, int[] depth) {
if (node == null) {
depth[0] = 0;
return true;
}
int[] left = new int[1], right = new int[1];
if (isBalanced(node.left, left) && isBalanced(node.right, right)) {
int diff = left[0] - right[0];
if (diff <= 1 && diff >= -1) {
depth[0] = 1 + (left[0] > right[0] ? left[0] : right[0]);
return true;
}
}
return false;
}
</code></pre>

<h4>思路：</h4>

通過遞歸求出左右節(jié)點(diǎn)的深度差值裙顽。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市宣谈，隨后出現(xiàn)的幾起案子愈犹，更是在濱河造成了極大的恐慌，老刑警劉巖闻丑，帶你破解...
    沈念sama閱讀 206,126評(píng)論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件漩怎，死亡現(xiàn)場離奇詭異，居然都是意外死亡嗦嗡，警方通過查閱死者的電腦和手機(jī)勋锤，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,254評(píng)論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來侥祭，“玉大人叁执，你說我怎么就攤上這事茄厘。” “怎么了谈宛？”我有些...
    開封第一講書人閱讀 152,445評(píng)論 0贊 341
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵次哈，是天一觀的道長。 經(jīng)常有香客問我吆录，道長窑滞，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 55,185評(píng)論 1贊 278
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任恢筝，我火速辦了婚禮哀卫，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘滋恬。我一直安慰自己聊训，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 64,178評(píng)論 5贊 371
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布恢氯。 她就那樣靜靜地躺著，像睡著了一般鼓寺。 火紅的嫁衣襯著肌膚如雪勋拟。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 48,970評(píng)論 1贊 284
  • 城市分裂傳說
    那天妈候，我揣著相機(jī)與錄音敢靡，去河邊找鬼。 笑死苦银，一個(gè)胖子當(dāng)著我的面吹牛啸胧，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播幔虏，決...
    沈念sama閱讀 38,276評(píng)論 3贊 399
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼纺念，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼！你這毒婦竟也來了想括？” 一聲冷哼從身側(cè)響起陷谱，我...
    開封第一講書人閱讀 36,927評(píng)論 0贊 259
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎瑟蜈，沒想到半個(gè)月后烟逊，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 43,400評(píng)論 1贊 300
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡铺根，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,883評(píng)論 2贊 323
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年宪躯，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片位迂。...
    茶點(diǎn)故事閱讀 37,997評(píng)論 1贊 333
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡访雪，死狀恐怖予颤，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情冬阳，我是刑警寧澤蛤虐，帶...
    沈念sama閱讀 33,646評(píng)論 4贊 322
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站肝陪，受9級(jí)特大地震影響驳庭，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜氯窍，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,213評(píng)論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一饲常、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧狼讨，春花似錦贝淤、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,204評(píng)論 0贊 19
  • 一樁弒父案播聪，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至布隔，卻和暖如春离陶，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背衅檀。 一陣腳步聲響...
    開封第一講書人閱讀 31,423評(píng)論 1贊 260
  • 情欲美人皮
    我被黑心中介騙來泰國打工招刨， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人哀军。 一個(gè)月前我還...
    沈念sama閱讀 45,423評(píng)論 2贊 352
  • 代替公主和親
    正文 我出身青樓沉眶，卻偏偏與公主長得像，于是被迫代替她去往敵國和親杉适。 傳聞我的和親對(duì)象是個(gè)殘疾皇子谎倔，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,722評(píng)論 2贊 345

推薦閱讀更多精彩內(nèi)容

  • 總結(jié) 想清楚再編碼 分析方法：舉例子、畫圖 第1節(jié)：畫圖分析方法 對(duì)于二叉樹淘衙、二維數(shù)組传藏、鏈表等問題，都可以采用畫圖...
    M_巴拉巴拉閱讀 1,204評(píng)論 0贊 7
  • 1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目： 輸入一棵二元查找樹彤守，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表毯侦。 要求不...
    曲終人散Li閱讀 3,294評(píng)論 0贊 19
  • 第1章 面試的流程 編程時(shí)應(yīng)注意的三點(diǎn)： 思考清楚再開始編碼； 良好的代碼命名和縮進(jìn)對(duì)齊具垫； 能夠單元測(cè)試侈离； 現(xiàn)場面...
    codingXue閱讀 473評(píng)論 5贊 0
  • 劍指offer(二) 面試題九：斐波那契數(shù)列 題目一：寫一個(gè)函數(shù)，輸入n筝蚕，求斐波那契數(shù)列的第n項(xiàng)卦碾，裴波納契數(shù)列的定...
    橋?qū)?/span>閱讀 305評(píng)論 0贊 0
  • 說明： 本文中出現(xiàn)的所有算法題皆來自牌涛耄客網(wǎng)-劍指Offer在線編程題，在此只是作為轉(zhuǎn)載和記錄洲胖，用于本人學(xué)習(xí)使用济榨，不...
    秋意思寒閱讀 1,145評(píng)論 1贊 1