二叉树专题 2016-7-22

[wolfogre]

111. Minimum Depth of Binary Tree 199. Binary Tree Right Side View 124. Binary Tree Maximum Path Sum

[zhaokuohaha]

111-dfs-C

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution
{
    public int MinDepth(TreeNode root)
    {
        if (root == null) return 0;
        int ld = MinDepth(root.left);
        int rd = MinDepth(root.right);
        if (root.left == null)
            return 1 + rd;
        else if (root.right == null)
            return 1 + ld;
        return 1 + Math.Min(ld, rd);

    }
}

[zhaokuohaha]

199 - dfs - C

先遍历右子数 每一步变量记录当前深度 & 更新最大深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution
{
    List<int> res;
    int maxDepth = 0;
    public IList<int> RightSideView(TreeNode root)
    {
        res = new List<int>();
        if (root != null)
            postOrderTraversal(root, 1);
        return res;
    }

    private void postOrderTraversal(TreeNode root, int depth)
    {
        if (depth > maxDepth)
        {
            maxDepth = depth;
            res.Add(root.val);
        }
        if (root.right != null)
            postOrderTraversal(root.right, depth + 1);
        if (root.left != null)
            postOrderTraversal(root.left, depth + 1);
    }
}

[wolfogre]

111 Minimum Depth of Binary Tree

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root)
        return 0;
    if(!root.left)
        return minDepth(root.right) + 1;
    if(!root.right)
        return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

[SnackMen]

/*
[AC] Minimum Depth of Binary Tree
*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        int leftCount = minDepth(root.left);
        int rightCount = minDepth(root.right);
        if(root.left==null)
            return ++rightCount;
        if(root.right==null)
            return ++leftCount;
        return 1+Math.min(leftCount,rightCount);
    }
}

[SnackMen]

 /*
 *  [AC]  199. Binary Tree Right Side View
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<Integer>();
        DFS(root,0,view);
        return view;
    }
   public void DFS(TreeNode root,int deepth,List<Integer> view){
        if(root==null)
            return;
        if(deepth==view.size())
            view.add(root.val);
        DFS(root.right,deepth+1,view);
        DFS(root.left,deepth+1,view);
   }
}

[wolfogre]

199 Binary Tree Right Side View

没有栈，没有队，自己给自己造。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

function Queue(size){
    this.size = size;
    this.dataStore = [];
    this.head = 0;
    this.tail = 0;

    this.push = function (element){
        if((this.tail + 1) % this.size === this.head)
            throw "Queue is full";
        this.dataStore[this.tail] = element;
        this.tail = (this.tail + 1) % this.size;
    };

    this.pop = function (){
        if(this.empty())
            throw "Queue is empty";
        this.head = (this.head + 1) % this.size;
    };

    this.peek = function(){
        if(this.empty())
            throw "Queue is empty";
        return this.dataStore[this.head];
    };

    this.empty = function (){
        return this.tail === this.head;
    }
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
     var result = [];
     if(!root)
        return result;

     var prev;
     var index = 0;
     var queue = new Queue(1000);
     queue.push(root);
     queue.push(new TreeNode(null));
     while(!queue.empty()) {
         if(queue.peek().val === null) {
             result[index++] = prev;
             queue.pop();
             if(!queue.empty())
                queue.push(new TreeNode(null));
         } else {
             prev = queue.peek().val;
             if(queue.peek().left) {
                queue.push(queue.peek().left);
             }
             if(queue.peek().right) {
                queue.push(queue.peek().right);
             }
             queue.pop();
         }

     }
     return result;
};

[wolfogre]

124 Binary Tree Maximum Path Sum

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

 function Result(maxLength, maxFar){
     this.maxLength = maxLength;
     this.maxFar = maxFar;
 }

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
    return maxPathSumHelp(root).maxLength;
};

var maxPathSumHelp = function(root) {
    if(!root)
        return new Result(Number.NEGATIVE_INFINITY, 0);
    var leftResult = maxPathSumHelp(root.left);
    var rightResult = maxPathSumHelp(root.right);
    return new Result(
        Math.max(leftResult.maxLength, 
                rightResult.maxLength,
                root.val, 
                leftResult.maxFar + root.val, 
                rightResult.maxFar + root.val,
                leftResult.maxFar + rightResult.maxFar + root.val),
        Math.max(root.val, 
                leftResult.maxFar + root.val,
                rightResult.maxFar + root.val)
    );

};

[dayang]

/**
 * [AC] 111 Minimum Depth of Binary Tree
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(root === null)
        return 0;
    if(root.left === null)
        return minDepth(root.right) + 1;
    if(root.right === null)
        return minDepth(root.left) + 1;
    return Math.min(minDepth(root.right),minDepth(root.left)) + 1;
};

[dayang]

/**
 * [AC] 199 Binary Tree Right Side View  宽度优先bfs
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(root === null)
        return [];
    let res = [];
    let queue = [];
    queue.push('#');
    queue.push(root);
    while(queue.length > 1){
        let node = queue.shift();
        if(node === '#'){
            queue.push('#');
            res.push(queue[0].val);
            continue;
        }
        if(node.right !== null)
            queue.push(node.right);
        if(node.left !== null)
            queue.push(node.left);
    }

    return res;
};

[zhaokuohaha]

124 - dfs - C

有点类似之前数组最大和那样的贪心算法, 每次求当前子树的最大和, 如果最大和小于0, 丢弃 回退时返回 和最大的一条路

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int res = 0;
    public int MaxPathSum(TreeNode root) {
        if(root != null){
            res = root.val;
            dfs(root);
        }
        return res;
    }

    public int dfs(TreeNode root){
        if(root==null)
            return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int val = root.val;
        if(left > 0 ) 
            val += left;
        if(right > 0 ) 
            val += right;
        res = res > val ? res : val; //以当前为根的最大和
        return Math.Max(Math.Max(root.val, root.val+left),root.val+right); //返回最大的一条路
    }
}