129. 求根到叶子节点数字之和

问题

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 \(1->2->3\) 代表数字 \(123\)。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: \([1,2,3]\)

    1
   / \
  2   3

输出: 25
解释:
从根到叶子节点路径 \(1->2\) 代表数字 \(12\).
从根到叶子节点路径 \(1->3\) 代表数字 \(13\).
因此,数字总和 = \(12 + 13 = 25\).
示例 2:
输入:\([4,9,0,5,1]\)

    4
   / \
  9   0
 / \
5   1

输出: \(1026\)
解释:
从根到叶子节点路径 \(4->9->5\) 代表数字 \(495\).
从根到叶子节点路径 \(4->9->1\) 代表数字 \(491\).
从根到叶子节点路径 \(4->0\) 代表数字 \(40\).
因此,数字总和 = \(495 + 491 + 40 = 1026\).

解法

整体难度不大,使用深度优先搜索算法递归即可

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return result;
    }
    
    private void dfs(TreeNode root, int curr) {
        if (root == null) {
            return;
        }
        //需要注意的是这里要乘10再加。
        curr = curr *10 + root.val;
        if(root.left ==null && root.right == null) {
            result += curr;
            return;
        }
        //递归左子树
        bfs(root.left, curr);
        //递归右子树
        bfs(root.right,curr);
    }
}
2019/07/30 22:28 下午 posted in  leetcode 二叉树 深度优先遍历

94. 二叉树的中序遍历

给定一个二叉树,返回它的中序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3

输出: \([1,3,2]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法(递归)

经典的算法题,没什么可说的。

代码(递归)

/**
 * 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> result = new LinkedList<>();
        mid(root, result);
        return result;
    }
    private void mid(TreeNode root, List<Integer> result) {
        if (root ==null) {
            return;
        }
        //先递归左子树
        mid(root.left,result);
        //递归完成后加入本节点
        result.add(root.val);
        //再递归右子树
        mid(root.right, result);
    }
}

解法(迭代)

构建一个栈,只要有左子树就一直压栈,直到左子树为空,出栈后将结果加入到result,然后将当前指针指向当前节点的右子树,进行下一轮压栈处理。

代码(迭代)

/**
 * 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> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            //左子树一直压栈
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            //出栈
            root = stack.pop();
            result.add(root.val);
            //切换到右子树进行下一轮
            root = root.right;
        }
        return result;
    }
}
2019/07/24 23:09 下午 posted in  leetcode 二叉树 深度优先遍历

144. 二叉树的前序遍历

问题

给定一个二叉树,返回它的 前序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3 

输出: \([1,2,3]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法

没什么可说的。直接上代码吧。

代码

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        preorder(root);
        return result;
    }
    
    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先将root.val加入result
        result.add(root.val);
        //递归左子树
        preorder(root.left);
        //递归右子树
        preorder(root.right);
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //需要注意这里right要先压栈 其他的基本无压力。
            if (node.right !=null) {
                stack.push(node.right);
            }
            if (node.left !=null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}
2019/07/20 19:04 下午 posted in  二叉树 leetcode 深度优先遍历

589. N叉树的前序遍历

问题

给定一个 \(N\) 叉树,返回其节点值的前序遍历。
例如,给定一个 \(3叉树\) :
 

返回其前序遍历: \([1,3,5,6,2,4]\)。

说明: 递归法很简单,你可以使用迭代法完成此题吗?

解法

如果忽略说明的话,使用递归确实非常简单。与二叉树的前序遍历一样,唯一需要注意的一点是儿子是个list。递归转迭代也只是用栈来缓存
下面给出递归与迭代的不同代码

代码

java

递归方式

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        dfs(root);
        return result;
    }
    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        //唯一需要注意的就是这里的对儿子的处理
        if (root.children !=null) {
            for(Node node:root.children) {
                dfs(node);
            }
        }
    }
}

迭代方式

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        //使用栈来存储
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);
            if (node.children !=null) {
                List<Node> children = node.children;
                //这里需要注意的一点是,压栈的顺序,要从最右开始压
                for(int i=children.size() - 1;i >= 0;i--){
                    stack.push(children.get(i));
                }
            }
        }
        return result;
    }
}
2019/07/16 21:59 下午 posted in  leetcode 深度优先遍历 dfs

110.平衡二叉树

问题

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树\([3,9,20,null,null,15,7]\)

    3
   / \
  9  20
    /  \
   15   7

返回\(true\)
示例 2:

给定二叉树 \([1,2,2,3,3,null,null,4,4]\)

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

返回\(false\)

解法

深度优先搜索,首先获取左右子树的深度,判断相差是否小于1,然后递归左右子树即可,需要注意的一点是获取左右子树深度的时候需要+1

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        //获取左子树的深度
        int left = dfs(root.left);
        //获取右子树的深度
        int right = dfs(root.right);
        
        //判断左右子树深度差 递归调用左右子树。
        return Math.abs(left-right) <=1 &&  isBalanced(root.left) && isBalanced(root.right);
    }
    //获取树的深度
    private int dfs(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        //左右深度+1的最大值。
        return Math.max(left, right) + 1;
    }
}
2019/07/16 00:24 上午 posted in  leetcode dfs 二叉树 深度优先遍历

687.最长同值路径

问题

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

**注意:**两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

      5
     / \
    4   5
   / \   \
  1   1   5

输出 \(2\)

示例 2:

输入:

      1
     / \
    4   5
   / \   \
  4   4   5

输出: \(2\)
注意: 给定的二叉树不超过\(10000\)个结点。 树的高度不超过\(1000\)。

解法

基本想法就是深度优先遍历。遍历时,判断左右儿子的值与自己的值是否相等,相等则result++,否则置为0即可。没有什么难度。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root != null) {
            dfs(root);
        }
        return result;
    }
    private int dfs(TreeNode root) {
        if (root ==null) {
            return 0;
        }
        
        //计算左子树的同值路径
        int left = dfs(root.left);
        //判断左儿子与自己的值是否相等,相等则++ 否则置为0
        if (root.left == null || root.val !=root.left.val) {
            left = 0;
        } else {
            left ++;
        }
        //计算右子树的同值路径
        int right = dfs(root.right);
        //同左儿子的判断
        if (root.right == null || root.val !=root.right.val) {
            right = 0;
        } else {
            right ++;
        }
        //需要注意的是这里的max为left+right与result的判断。
        result = Math.max(left + right,result);
        return Math.max(left, right);
    }
}
2019/07/15 23:54 下午 posted in  dfs 二叉树 leetcode 深度优先遍历

543.二叉树的直径

问题

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

digraph G {
    { 
        node [margin=0 width=0.1 shape=circle style=filled] 
        1 -> 2  [arrowhead=none]
        1 -> 3  [arrowhead=none]
        2 -> 4  [arrowhead=none]
        2 -> 5  [arrowhead=none]
    }
}

返回\(3\),它的长度是路径 \([4,2,1,3]\) 或者 \([5,2,1,3]\)。

**注意:**两结点之间的路径长度是以它们之间边的数目表示。

解法

此题是二叉树深度搜索的扩展,考虑设置一个全局变量result,每次递归时判断一次左子树深度+右子树深度 是否大于result,如果大于,那么将result替换成和,递归完成时,返回result即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 深度优先遍历+判断一次result大小即可。
        dfs(root);
        return result;
    }
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //递归左子树
        int right = dfs(root.right);
        //递归右子树
        int left = dfs(root.left);
        //左子树深度+右子树深度就是走过当前节点的直径长度
        if (left + right > result) {
            result = left + right;
            
        }
        //返回当前节点深度+1.递归到上一层参与计算
        return Math.max(left, right) + 1;
    }
}
2019/07/15 15:16 下午 posted in  二叉树 dfs 深度优先遍历 leetcode